I'm interested in solving the following system of equations over the integers:

\begin{align*} x_l^3 &\le x_l^1x_l^2 & \text{ for } l = 1,\ldots,s \\ A x &\le b \\ 0 &\le x \end{align*} where $x_l^j$ are components in $x$. There are methods to solve the case where $x_l^1 = x_l^2$. But I know of no analogous results for the "hyperbolic" case. My main interesting is in checking that there is a small solution.


1 Answer 1


One classic technique is to reformulate the integer variables as a bunch of binary variables. In this case i would use a encoding with powers of 2 and then use a multiplier circuit to express the multiplication. Since multiplicaiton circuits are made out of ANDs and ORs the resulting problem will be MILP.

Bi-linear terms (and also monomial terms which all can be expressed as nested bi-linear terms) can be over approximated using McCormick envelopes. Some MINLP solvers (i am aware that Alpine.jl does that) use this to express products.

I would recommend throwing some MINLP solvers at is first and see how they do. If that proves infeasible see if you have success with a binary linear formulation and see if MILP solvers help you. If all your variables are binary and MILP solvers fail to find feasible solutions try Exact.

  • $\begingroup$ Thanks for your answer. I was looking for methods that solve this specific case similar to the method proposed in the linked paper. $\endgroup$ May 4, 2022 at 17: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.