0
$\begingroup$

I am trying to simulate the following quadratic integer program using $\textsf{cvxpy}$:

$$ \begin{array}{ll} \underset {x_1, \dots, x_K} {\text{minimize}} & \displaystyle\sum\limits_{i=1}^{K}\frac{y_{i}}{Y}\left(\frac{x_{i}}{y_{i}}-\frac{X}{Y}\right)^{2} \\[0.2cm] \text{subject to} & x_{i} \leqslant y_{i}, \quad i=1, 2, \dots, K \\ & \sum_{i}x_{i}=X \\ & x_{i}, y_{i} \in \mathbb{Z}^{+}, \quad i=1,2,\ldots,K\end{array} $$

where $\sum_{i=1}^{K} y_{i} = Y$. There is a paper by Bretthauer et al. (1995) where they address this type of problem and proposed a good algorithm to solve this. However, I chose to use $\textsf{cvxpy}$ for simplified and optimized simulation.

Accordingly, I wrote the following piece of code:

import numpy as np
import cvxpy as cp

def solve_quad_int_knapsack(y, X):

    Y = np.sum(y)
    m = X/Y

    x = cp.Variable(len(y), integer=True)  # Integer variables x_i

    objective =  cp.sum((y/Y) * cp.square(x/y - m))  # Objective function
    constraints = [0 <= x, x <= y, sum(x) == X]

    problem = cp.Problem(cp.Minimize(objective), constraints)
    res = problem.solve()

    obj = objective.value
    x_optimal = x.value

    return obj, x_optimal

In simulating the code for $y=\begin{bmatrix}10&18&41 \end{bmatrix}$ and $X=12$, I received the following error:

SolverError: Either candidate conic solvers (['GLPK_MI', 'SCIPY']) do not support the cones output by the problem (SOC, NonNeg, Zero), or there are not enough constraints in the problem.

Can someone please help me understand the error that seems to be with the linear constraints?

$\endgroup$
0

1 Answer 1

2
$\begingroup$

The constraints are fine.

Per the CVXPY "Choosing a solver" table, neither GLPK_MI nor SCPY support QP. You need a solver in that table having an X in both the QP and MIP columns.

The error message seems unnecessarily non-specific and therefore confusing as to the actual error. But don't blame me, I am not a CVXPY developer.

$\endgroup$
1
  • 2
    $\begingroup$ I chose $\textsf{GUROBI}$ and it worked! $\endgroup$
    – UserX
    May 28 at 15:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.