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?
