2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ In python @ is for matrix multiplication and * is for scalar multiplication and element-wise matrix multiplication. "Scalar" does not mean that r1_pri and r2_pri are constants, but means that they are not vectors or matrices (of no matter constants or variables). $\endgroup$
    – xd y
    Jan 3, 2023 at 2:15
  • $\begingroup$ Heuristic solution of non-convex QP in CVXPY should be possible using either github.com/cvxgrp/qcqp or github.com/cvxgrp/dmcp .. I don't know that either of these methods would necessarily work well. on this problem. The best approach might be to use a tool which allows for non-convex QP, used in conjunction with a local or global QP (or general NLP) optimization solver. $\endgroup$ Jan 11, 2023 at 15:28

1 Answer 1

-1
$\begingroup$

In math programming whenever two variables are summed up or any kind of operation is conducted (-,*) and the resultant is used again in another operation, then it should be declared a variable. So separation_penalty should be declared as a variable first.
So if $z=xy$ and again penalty= $dist*z$ then $z$ should be declared a var.
Only if $z$ is going to be used as objective without any further operation then it need not be declared a variable. It will be akin to like obj = $xy$ instead of obj = $z$.

$\endgroup$
3
  • $\begingroup$ Casting the result as cp.Variable(z) was ineffective as the CVXPY class method was not expecting a variable as an input; it expected parameters such as shape. Not sure how to register new variables with the library if that's required. $\endgroup$
    – jbuddy_13
    Dec 4, 2022 at 0:12
  • $\begingroup$ Ok, was casting $z=xy$ as a constraint helpful? And then use z*dist as an objective expression. $\endgroup$ Dec 4, 2022 at 0:39
  • 3
    $\begingroup$ The first part of the answer "the resultant must be declared a variable to be used" is wrong, CVXPY is a modeling tool and even in a solver it is not necessary. The second part "writing z=xy" will not help since it is not convex. The product x*y is a nonconvex function of x,y so this is not for CVXPY nor for a convex solver. $\endgroup$ Dec 6, 2022 at 9:39

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.