2
$\begingroup$

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.

Seat distance matrix

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.

Seat distance matrix

$\endgroup$
4
  • 1
    $\begingroup$ Gurobi has an option/parameter to recall current solution, add that as a constraint and run the model. in formulation, you just have to $Sz$ as a variable not available, say #Sz = 0$. Now what's not clear, you say viewers $i$ and $j$ to be given seats S4, S9. i and j are some index if viewers? $\endgroup$ Dec 1, 2022 at 19:11
  • $\begingroup$ Sounds like this is actionable in 2 parts: 1/ Constrain seats, Sz=0 and 2/ add to objective function, maximize distance of Si to Sz using something similar to +1 * [ Si * D[i,z] ]. Yeah? $\endgroup$
    – jbuddy_13
    Dec 1, 2022 at 19:27
  • $\begingroup$ Yes, makes sense. My previous comment got a bit jacked. I am not clear about viewers i & j being allotted to red/blue seats. $\endgroup$ Dec 1, 2022 at 20:00
  • $\begingroup$ Ah, red vs blue is just for illustrative purposes. In practice there is no difference in seats. However, to account for all seat combinations, I expect to use a nested for loop, accounting for all possible seat combinations. However, this may be unnecessary or outright wrong with a variable number of viewers, say 5. $\endgroup$
    – jbuddy_13
    Dec 1, 2022 at 20:02

2 Answers 2

2
$\begingroup$

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}$

$\endgroup$
3
  • $\begingroup$ I'm gathering that this is impossible for a linear solver due to dependency on product xi*xj. Do you recommend CVXPY (or an alternative) for quadratic programming in Python? $\endgroup$
    – jbuddy_13
    Dec 1, 2022 at 23:12
  • $\begingroup$ Hold on there's a way to linearize it $\endgroup$ Dec 1, 2022 at 23:22
  • 1
    $\begingroup$ Edited to linearize x's $\endgroup$ Dec 1, 2022 at 23:36
2
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Very insightful tips! One comment/question: Suppose there are 5 viewers who need to be allocated seats, I conceived of viewer_i and viewer_j as a nested for loop to account for all possible seat-distance combinations. The optimal output, however, would allocate 5 seats. Does this detail dramatically change the construction of the problem? $\endgroup$
    – jbuddy_13
    Dec 1, 2022 at 20:09
  • $\begingroup$ Further red & blue were used as a mechanism to visualize the collective penalties associated with a given seat-seat combination at an arbitrary point in the nested for loop mentioned above. (Ultimately, seats are not of different categories or values) $\endgroup$
    – jbuddy_13
    Dec 1, 2022 at 20:12
  • $\begingroup$ For my real world problem, an unequal assignment of viewers to F1 or F2 is immaterial; it is assumed that distance from F1 and distance from F2 incur equal penalties. So minimizing average distance, as you proposed, should be sufficient. $\endgroup$
    – jbuddy_13
    Dec 1, 2022 at 20:16
  • 1
    $\begingroup$ Depending on the details of your problem, you will either have a binary variable $X_s$ for each seat $s$ (did we assign someone to the seat) or a binary variable $X_{v,s}$ for each combination of viewer $v$ and seat $s.$ In formulating the proximity portion of the objective function, you will either loop through all pairs $X_s,X_{s'}$ with $s\neq s'$ or all pairs $X_{v,s},X_{v',s'}$ with $v\neq v'$ and $s\neq s',$ taking products of the variables. It does not change the model construction qualitatively, just the size of the model. $\endgroup$
    – prubin
    Dec 1, 2022 at 21:00
  • $\begingroup$ I took at stab at this using OR tools; I think you're right that there won't be a way around using a quadratic solver given the occupancy pairs issue which you noted in your answer/comments. (or.stackexchange.com/questions/9455/…) $\endgroup$
    – jbuddy_13
    Dec 1, 2022 at 22:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.