# Applying weights to assignment problems for linear MIP solvers

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

• You are welcome. I'd try to put something in the answer today. Commented Dec 2, 2022 at 12:46

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

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

• I made an update to the prompt to capture an issue I ran into; I might actually need a quadratic solver. The context is Z[i,j] (from previous solution) captures whether both seats i and j have viewers. When applying a distance penalty, proportional to viewer priority, the penalty is applied whether seat i or seat j has a viewer; in reality, the penalty should be zero unless both seats have viewers. Commented Dec 2, 2022 at 22:16
• Pls check if model below 2nd edit in my answer solves the issue satisfactorily. Commented Dec 2, 2022 at 23:17
• Edited couple of constraints, had typed it wrongly before. Commented Dec 3, 2022 at 13:36
• Viewerpri is the same viewer_pri that you computed- priority score of viewer v if seat i is assigned. Mathjax confuses if I use viewer_pri. Constraint works like with M acting as bigM, the sum of priority scores of 2 viewers is constrained to 0 if one of seats remains unassigned, $\sum_v v_{i,v}=0$ or $\sum_v v_{j,v}=0$. Commented Dec 3, 2022 at 14:53
• About M, yes right take. You have priority scores, so can take sum of two highest+1, nothing can be greater than that for two seats. Idea is not to use a number which is so big that it effects performance or disturbs the scale of the model. Commented Dec 3, 2022 at 15:04