Mixed Integer Programming: Iterative assignment problem

Question

I have a real world problem, which is analogous to the below toy problem, which I call 'The Movie Theater Problem' (TMTP.)

In TMTP, movie viewers are assigned seats which principally balances two objectives, weighted equally: 1/ minimize distances to fire exists (F1 and F2) and 2/ maximize distance from other viewers, allocated to seats (S1...S9). For viewers, i (red) and j (blue) the proposed seats are S4 and S9, respectively, as depicted below.

Notes:

1. Distance/Angle to theater screen is irrelevant as this is a toy problem analogous to one that is of interest to me.
2. The sum of viewers could be any number, less than or equal to the total number of seats, not constrained to 2 viewers.
3. In practice, this solution could be called several times iteratively as new viewers purchase tickets. As such, some seats may be allocated in previous iterations, which must be factored in as constraints in the current iteration, and are not eligible for the solver to reallocate.
4. I typically use Google's OR-Tools, which interface with various MIP solvers, as well as CP-SAT, a constraint programming solver, which could potentially be more appropriate.

Data structures

The primary data structure of interest is D, a distance matrix, where D[i,j] represents the distance between locations i->j.

#     F1, S1, ..., S9, F2   
D = [[                   ], #F1
     [                   ], #S1
     ...
     [                   ], #S9
     [                   ]] #F2

Objective Function. I cannot directly minimize Eq1 and maximize E2 at the same time, however, scaling Eq1 by -1, should allow for a single objective function to be maximized where the dual of Eq1 is minimized.

Max( -1 * [  Si * D[i,F1]
           + Si * D[i,F2]
           + Sj * D[j,F1]
           + Sj * D[j,F2]  ] 
     +1 * [  Si * Sj * D[i,j] ] )

Constraints

Si in {1,0}
Sj in {1,0}
Si != Sj
SUM(Si: 1->n) = num_viewers 

Questions:

1. How can I best articulate this as a (mixed) integer programming problem?
2. Is my objective function appropriate given the textual write-up above?
3. Are my constraints (thus far) valid?
4. How can I add constraints for seats that are already allocated from previous iterations, Sz?
5. Is constraint programming more suitable than a MIP solution?

A second version of this graphic is provided where S3 is allocated already, so distances from it must be maximized, but unlike Si and Sj, Sz cannot be allocated elsewhere and is a fixed constraint.

Answer 1

With V = no. of viewers as variable, S =9 -$x_s$ from previous iteration, as constant
$x_s$ is binary $\in\ {0,1}$ flipping to 1 if seat, s is assigned
$z \in\ {0,1}$ as well to make sure seats are enough for viewers. Otherwise solver will make everything 0.

Constraints
C1 = $S - V \le Mz$
C1_1 = $V-S \le M(1-z)$

C2 = $Vz+S(1-z) = \sum_s x_s $ : If V<S, allocate V seats, else allocate all S seats.

Objective

$Average \ Exit$ = ${\sum_s \sum_{f=[1,2]} D_{f}x_s}\over S$
$Viewer \ Dist$ = $\sum_{i,j \in\ S\times S} \ D_{i,j}x_ix_j$

Obj = $min (scale(Average \ Exit) - Viewer \ Dist)$

Linearize the obj
Introduce $z_{i,j} \in\ {0,1} \ \forall i,j \in\ seats \ S$

Additional constraints
$z_{i,j} \le x_i$
$z_{i,j} \le x_j$
$ x_i + x_j - 1 \le z_{i,j}$

In the objective part Viewer Dist, replace $x_ix_j$ with $z_{i,j}$

Answer 2

The following is expressed in terms of the "toy" problem, and may or may not translate to your actual problem.

If you are going to use a single objective function, there are some questions to answer. First, do you want to use the distance from each viewer to the nearest fire exit, or the sum/average distance to all fire exits? Another possibility (which would complicate the objective function) would be the distance to nearest weighted by the number of viewers for whom that is the nearest exit. (An exit being close is less helpful if everyone else is trying to get out that door.) Similarly, do you care about the distance from a given viewer to the closest other viewer, the total/average distance to all other viewers, or the number of viewers within a certain distance.

Second, once all that is thrashed out, is how to weight the combination of the two distances in the objective function. Simply subtracting the exit distance expression from the viewer distance expression might not be adequate. Even though both may be expressed in the same units, a decrease of one foot distance to a neighboring viewer might not be as painful/annoying as an increase of one foot distance to the nearest fire exit.

Third, you have to decide if all viewers are equivalent (meaning red in seat 4, blue in seat 9 is functionally the same as blue in seat 4, red in seat 9).

Once you've worked through that, you will have a version of the quadratic assignment problem if viewers have to be treated as individuals (meaning it matters which viewer is in seat 4, rather than just that seat 4 is filled). If all that matters is which seats are filled, it's a simpler model, but the objective is still quadratic because the distance measure depends on the occupancy of pairs of seats.