This question is a Google OR-Tools specific implementation of recommendation from a previous question.

In short, the movie theater problem encompasses assigning viewers to seats such that the distance between viewers is maximized, however, the distance between viewers and fire exits is minimized. I've attempted to solve using OR-Tools, specifically the SCIP solver: Google Colab (reference for full code/details.)

The expert of interest is below:

objective_terms = []

## Seat-seat distance penalty
for i in seat_matrix.keys():
  # only compute the penalty once per each {seat_i, seat_j} pair
  if i == max_seats:
  seat_i = seat_vars[i]

  for j in range(i+1, max_seats+1):
    seat_j = seat_vars[j]

    # only apply the distance penalty(i,j) if both seats i and j are assigned
    # unless both binary variables equal 1, penalty is not applied
    ## Attenpt 1: Triggers error
    dist = distance_matrix[(i,j)] * seat_i * seat_j 

    ## Attempt 2: Doesn't apply penalty
    # if seat_i + seat_j == 2:
    #   objective_terms.append(distance_matrix[(i,j)])

## Seat-exit distance penalty 
for seat,var in seat_vars.items():
  dist = exit_distance_matrix[(seat, 1)] * var + exit_distance_matrix[(seat, 2)] * var


solution = {}
for seat, var in seat_vars.items():
  solution[seat] = var.solution_value()

Both attempt 1 and attempt 2 fail but for different reasons: Attempt multiplies two integer variables, which violates the assumption of linearity. Attempt 2 fails because the conditional logic is not accepted.

How can these objective functions be restated such that seat-seat distance penalty is only applied if both seat_i and seat_j equal 1.

  • 1
    $\begingroup$ Edited on the other question on linearizing x's $\endgroup$
    – Sutanu
    Dec 1, 2022 at 23:41

1 Answer 1


Basically as earlier
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}$


Your Answer

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

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