I have a quadratic integer programming assignment problem. The goal is to assign riders seats on a bus such that distance between any two riders is maximized; however, the importance of each objective term (rider-rider distances) will be be scaled by the product of their priority scores, for example, elderly, disability, pregnancy, etc.
This problem is analogous to a real world problem, which I am solving. The bus-seat example is fictitious, however, it illustrates the nature of my constraints and objectives nicely.
I have attempted to solve this problem using CVXPY, however, then I get the following error:
DCPError: Problem does not follow DCP rules. Specifically:
The objective is not DCP. Its following subexpressions are not: (var7596[0] @ 5.0 + var7596[1] @ 4.0 + var7596[2] @ 3.0 + var7596[3] @ 2.0 + var7596[4] @ 1.0) @ (var7597[0] @ 5.0 + var7597[1] @ 4.0 + var7597[2] @ 3.0 + var7597[3] @ 2.0 + var7597[4] @ 1.0)...
Data
# Data
rider_priorities = {1:5,2:4,3:3,4:2,5:1}
num_riders = len(rider_priorities)
x_wide, y_tall = 5,5
max_seats = x_wide * y_tall
num_seats = 0
seat_matrix = {}
for i in range(1, x_wide+1):
for j in range(1, y_tall+1):
num_seats +=1
seat_matrix[num_seats] = (i,j)
import math
distance_matrix = {}
for i in seat_matrix.keys():
i_x, i_y = seat_matrix[i]
for j in seat_matrix.keys():
if i==j:
continue
j_x, j_y = seat_matrix[j]
euc_dist = math.sqrt((i_x - j_x)**2 + (i_y - j_y)**2)
distance_matrix[(i,j)] = euc_dist
And the actual problem formulation.
# Variables
seat_rider_map = {}
for s in range(1, num_seats+1):
seat_rider_map[s] = cp.Variable(shape=num_riders, boolean=True)
# Constraints
constraints = []
for seat, rider_arr in seat_rider_map.items():
# each seat assigned 0 or 1 riders
c = sum(rider_arr) <= 1
constraints.append(c)
# each rider assigned exactly one seat
for r in range(num_riders):
seat_arr = [seat_rider_map[seat][r] for seat in seat_rider_map.keys()]
c = sum(seat_arr) == 1
constraints.append(c)
# Objective
objective_terms = []
for s1 in range(1, max_seats):
for s2 in range(s1+1, max_seats+1):
r1_pri = sum([seat_rider_map[s1][r1-1] * p1 for r1,p1 in rider_priorities.items()])
r2_pri = sum([seat_rider_map[s2][r2-1] * p2 for r2,p2 in rider_priorities.items()])
# old formulation
# separation_penalty = r1_pri * r2_pri * distance_matrix[(s1,s2)]
#new formulation
separation_penalty = r1_pri @ r2_pri
separation_penalty *= distance_matrix[(s1,s2)]
objective_terms.append(separation_penalty)
objective = cp.Maximize(sum(objective_terms))
prob = cp.Problem(objective, constraints)
prob.solve()
solution = {}
for seat, rider_arr in seat_rider_map.items():
solution[seat] = rider_arr.value
I've seen other questions related to this error and answers have been about the function not being quadratic. However, as you can see from the error above, the terms are in fact quadratic.
In the objective function, r1_pri and r2_pri are both summations of variables scaled by constants. Then r1_pri and r2_pri multiplied (only quadratic operation) and scaled by a constant. The objective is to maximize the summation of these constants.
Could this error be triggered by something unrelated to non-quadratic operations? What does a solution look like?
Edit: With the new formulation, I get an error from separation_penalty = r1_pri @ r2_pri
: ValueError: Scalar operands are not allowed, use '*' instead
.
This is highly unexpected because this statement is a multiplication of two different variables, not constants.
@
is for matrix multiplication and*
is for scalar multiplication and element-wise matrix multiplication. "Scalar" does not mean thatr1_pri
andr2_pri
are constants, but means that they are not vectors or matrices (of no matter constants or variables). $\endgroup$