Applying weights to assignment problems for linear MIP solvers

Question

In previous posts, A & B, I posed the Movie Theater Problem. 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.

In particular, the answer from @sutanu was helpful as they described a method for linearizing what appeared to be a quadratic problem. The solution has been implemented in Google Colab

I'd like to extend the solution to a variation of the movie theater problem, namely, that viewers' priority scores, according to a loyalty program, influence the objective function:

1. Maximize distance between viewers, proportional to their priority scores
2. Minimize distance between viewers and fire exits, F1 and F2, also proportional to priority scores.

In the previous iteration of the problem, solved in Google Colab, viewers implicitly shared the same priority score (all weights equaled 1.)

My previous objective function, in pseudo-code utilized a binary matrix of shape [seats, seats] where Z[i,j]=1 represents an edge between seat i and seat j (both seats were occupied and thus the viewer distance penalty was applied, else 0 penalty.)

Max( -1 * [  S[i]   * D[i,F1]    # distance seat i from F1 
           + S[i]   * D[i,F2]]   # distance seat i from F2
     +1 * [  Z[i,j] * D[i,j] ] ) # distance viewer i from viewer j 

This was possible by asserting two constraints that Z[i,j] <= S[i] and Z[i,j] <= S[j].

I'm unsure how to incorporate priority scores when making allocation decisions. How is it recommended to most easily achieve this effect?

Edit

I've made an attempt to solve this problem.

objective_terms = []

## Seat-seat priority-distance  penalty
# only compute the penalty once per each {seat_i, seat_j} pair
for i in range(1,max_seats):
  for j in range(i+1, max_seats+1):

    # 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

    viewer_pri_i = solver.Sum([V[i, v] * viewer_priorities[v] for v in range(1, num_viewers+1)])
    viewer_pri_j = solver.Sum([V[j, v] * viewer_priorities[v] for v in range(1, num_viewers+1)])
    weighted_distance = distance_matrix[(i,j)] * (viewer_pri_i + viewer_pri_j)
    objective_terms.append(weighted_distance)     

## 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(-0.5*dist) # average distance (seat, F1), (seat, F2)

As you can see, the seat separation penalty must be proportional to the viewer priority (aka higher priority seaters get more space, are closer to exits, etc.)

The line weighted_distance = distance_matrix[(i,j)] * (viewer_pri_i + viewer_pri_j) captures an error that I noticed: The separation penalty for i->j will be applied if either seat i or seat j has a viewer seated. It does not require both viewers to be seated.

See full code

Answer 1

Ok, since priority scores are associated with viewers need to create a set (tuple) of combinations SV with variables $x_{s,v} \ where \ v \in\ $ viewer V and $x_{s,v} \in\ {0,1} \ \forall s \in\ $Seats, S.
Any solver that can recall solved values of previous run can update S and python can dynamically make such combinations.
Constants/Parameters:
$p_v$ as priority score for every v $\in\ $V

Assuming previous constraints remain valid & relevant
Additional Constraints:

C1 = $\sum_{s}^S x_{s,v} \le 1 \quad \forall v \in\ V$: Ensure all viewers are assigned atmost 1 seat, where S = no. of seats available in current iteration
C2 = $\sum_v x_{s,v} \le 1 \quad \forall s \in\ S$

Objectives
Fire_Exit = Min$({\sum_{s,v \in\ SV} \sum_f D_fx_{s,v}\over S} - \sum_{s,v \in\ SV} p_vx_{s,v})$

A kind of experimentation may be needed here. I'd suggest, break the objectives into two parts
First solve with above objective. Then use optimal solution of this part as a constraint $\le$ in the next part for max dist between viewers. In next part priority portion will be $+$ to inter-viewer distance.
Need to check if this method gives better solution.

2nd Edit
Per the solution algorithm, for all $i,j \in\ $Seats,there are two variables:$viewerpr_{i,i}$ and $viewerpr_{i,j}$
that are multiplied with sum if priority $p_v$. So introduce a binary variable $z_{i,j}$ where Constraints:
$viewerpr_{i,i}+ viewerpr_{i,j} \le M\sum_v V_{i,v} \quad \forall i \in\ S$
$viewerpr_{i,i}+ viewerpr_{i,j} \le M\sum_v V_{j,v} \quad \forall j \in\ S$
M is sum(2 highest priorities)+1

Objective = $\sum_j \sum_i D_{i,j}(viewerpr_{i,i}+ viewerpr_{i,j})$