# How to solve this mixed integer quadratic program using cvxpy or other method?

My problem is described in this picture: $$\begin{array}{l} \left\{\begin{array}{l} \text { objective function: } \\ f = \min \sum_\limits{l=1}^2 \sum_\limits{i=0}^{2^l-1} \sum_\limits{j=0}^{2^l-2}\left(A_{i j}^l / A_{j +l}^l-D_{i j}^l / D_{ijH}^l\right)^2 \\ \text { constraints: } \\ A_{i j}^l-A_{2i \ 2j}^{l+1}-A_{2iH \ 2 j}^{l+1}-A_{2i \ 2jH}^{l+1}-A_{2iH \ 2jH }^{l+1}=0 \\ A_{i j}^l \leqslant V_{i j}^l \\ \end{array}\right. \end{array}$$

In this problem, D and V is known, A is the object that I want to get. It is a layered structure, each block in the upper layer is divided into four sub-blocks in the figure below.

What I want to do is simulate the distribution of D with A, so in the objective function is the ratio of two adjacent squares in each row in A compared to the value in D. I do this comparison on each layer and sum them. Then it is all of my objective function.

Also I have two constraints. The first is in A the value in the upper cell is equal to the sum of the four child nodes in the lower layer, just like the D and V. The second is the value in A is no more than the value in V in the same position.

I have tried the CVXPY library in python. But it seems my objective function is not a convex function so it can't solve it. My code is like:

first_layer = cp.Variable((2,2), integer=True)
second_layer = cp.Variable((4,4), integer=True)

for i in range(0,2):
for j in range(0,1):
cost += (first_layer[i][j] / first_layer[i][j+1] - D[1][i][j] / D[1][i][j+1])**2

for i in range(0,4):
for j in range(0,3):
cost += (second_layer[i][j] / second_layer[i][j+1] - D[2][i][j] / D[2][i][j+1])**2

constraints = []
for i in range(0,2):
for j in range(0,2):
constraints += [A[i][j] - A[2*i][2*j] - A[2*i+1][2*j] - A[2*i][2*j+1] - A[2*i+1][2*j+1] == 0]

for i in range(0,2):
for j in range(0,2):
constraints += [A[i][j] - V[i][j] <= 0]

objective = cp.Minimize(cost)
prob = cp.Problem(objective,constraints)
prob.solve(solver='ECOS_BB')


And the result is:

cvxpy.error.DCPError: Problem does not follow DCP rules. Specifically:
The objective is not DCP. Its following subexpressions are not:


It seems I violation the DCP rules [https://www.cvxpy.org/tutorial/dcp/index.html], because it saysexpr1*expr2, expr1/expr2, and expr1@expr2 can only be DCP when one of the expressions is constant.My objective function has the term x1/x2 so it can't works. But is DGP rules [https://www.cvxpy.org/tutorial/dgp/index.html] or DQP rules[https://www.cvxpy.org/tutorial/dqcp/index.html] works? I'm not sure.

So, I really don't know how to solve this type of problem? I'm even not sure it is what type of question. What type of objective function is this and how can I solve it?

• Welcome to OR.SE. It would be good if you can format your objective function and constraints using MathJax: or.meta.stackexchange.com/questions/5/… Commented Nov 28, 2022 at 17:39
• I have attempted to convert part of your text to MathJax to help you get started. Please check it for correctness and convert the remaining image to an array. Thanks. --- PS: Next time (don't!) upload a higher resolution image; convert images containing MathJax, tables and text to MathJax.
– Rob
Commented Nov 28, 2022 at 18:08
• Thank you! I will consider next time. Commented Nov 29, 2022 at 7:58
• What is the motivation for this question? Where does this optimization problem come from? Commented Nov 29, 2022 at 17:41
• It comes from a scatter plot sampling problem. Commented Nov 30, 2022 at 2:29

Maybe work with a slightly different objective. Basically, you want:

$$A_{i j}^l / A_{j +l}^l \approx D_{i j}^l / D_{ijH}^l$$

You could do:

$$\min \sum |A_{i j}^l - A_{j +l}^l \cdot D_{i j}^l / D_{ijH}^l |$$

This is now linear (CVXPY can linearize the absolute value for you).

A detail: maybe exclude: $$A_{j +l}^l=0$$. That may need an extra binary variable if $$A$$ can be negative. (I am not sure how you want to interpret $$A_{j +l}^l=0$$).

Note that this approach will give somewhat different solutions than your model. But it will do a similar thing. If you want to stick to your objective, I think you may need to look at a different tool, such as a (global) MINLP solver.

• Thank you. It helps me a lot!! Commented Nov 30, 2022 at 2:28

Try with constraint:
$$x_{i}*y_{i}=1$$.
Then replace $$x_i$$ with $$y_i$$ in the objective.