# Simulating an integer quadratic knapsack problem

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

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.

• I chose $\textsf{GUROBI}$ and it worked! May 28 at 15:44