Operations Research Stack Exchange is a question and answer site for operations research and analytics professionals, educators, and students. It only takes a minute to sign up.
Sign up to join this community
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.
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.
