2
$\begingroup$

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.

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

1 Answer 1

3
$\begingroup$

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

$\endgroup$

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.