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:
continue
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
objective_terms.append(dist)
## 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
objective_terms.append(-1*dist)
solver.Maximize(solver.Sum(objective_terms))
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.
