Is it possible to solve this rational non-convex MIP?

the minimization problem is given by

\begin{array}{cl} \min_{x,y} &\displaystyle\sum_{i=1}^{K} \frac{y_{i}}{Y}\left[\frac{x_{i}}{y_{i}} - \frac{X}{Y}\right]^2 \\ s.t& \sum_{i=1}^{K} x_{i} = X \\ &\sum_{i=1}^{K}y_{i}=Y \\ & x_{i}\leqslant y_{i}\\ &x_{i},y_{i}\in\mathbb{Z}^{+} \end{array}

The problem is non-convex and highly rational. If we were to fix one of the variables then CVXPY can solve this easy. However, I am wondering if theres a way around to solve problem if we can reformulate the objective function and constraint in another way.

There must be some constraints/bounds you are not telling us about, since this problem can be solved analytically.

1 Like

I have edited the constraints after I forgot an additional constraint. Thank you for the notice, I think the most important detail is that the decision variables are both positive and that one is always a bound to other.

For the sake of simplification I am mainly interested in the case of K=3. This somewhat resembles the quadratic integer knapsack problem which was addressed by Bretthauer et al. (1995). However, this problem becomes highly rational and non-convex.

So X,Y are constants? Then the objective develops (up to constant stuff we can ignore) to \sum_i \frac{x_i^2}{y_i} which is a sum of quad_over_lin so it is a natural mixed-integer SOCP. You can just input it as is.

Hmm, I see. Alternatively, if we define z_{i}\triangleq\frac{1}{y_{i}} and we instead minimize \sum_{i} z_{i}Y(x_{i}z_{i} - m)^{2} subject to x_{i}z_{i}-m=0 and \sum_{i}x_{i}=X and x_{i} z_{i}\leqslant 1 would this work with some CVXPY optimizer? The constraints are bi-linear.

I don’t understand what you are trying to achieve. It looks like overcomplicating a simple matter. For example how will you include the integrality constraint on y through z.

All mixed-integer SOCP optimizers under CVX and CVXPY will be able to solve the formulation I proposed.

I agree with your assertion. Thank you very much for your suggestions I will implement the code now!

Hello once more, I tried using quad_over_lin, but based on the arguments I have β€˜x’ and β€˜y’, the latter is a vectir not a scalar (I am facing an error saying that the second argument must be scalar). The idea is that I want the computations of x and y to be scalar as I am eventually computing the term \sum_{i}\frac{x_{i}^{2}}{y_{i}} for each i which is a scalar. Thus, the problem is that \textsf{obj = cp.sum(cp.quad_over_lin(x,y))} does not work.

You are asking a CVXPY question on the CVX forum.

But anyway, you just have to do it index by index then, something like

obj = cp.sum(cp.quad_over_lin(x[i],y[i]) for i in range(n))

or whatever of this kind compiles.

1 Like