Semidefinite programs (SDP) have an "efficient" solution, as a convex problem, by e.g. the ellipsoid method; but this comes with standard caveats as the output can be exponentially long (there is a problem of size $O(n)$ that requires integers that are $O(2^n)$ bits). All the same, it admits an exponential-time algorithm to some precision, and Tarski's generic algorithm for satisfiability over the reals means that it can be decided exactly.

Integer Linear Programs are NP-hard, but admit a very straightforward exponential-time search if all the variables have bounds; when they don't have bounds, there are still exponential time algorithms.

A natural question is: what happens when these are combined? I can find essentially no theoretical results on the question.

When quadratic constraints are present (MIQP), if the quadratic terms are non-convex, the problem is undecidable (because you can create arbitrary polynomials). I can't find any information on what happens they are convex.

There's some literature on practical software implementations to solve bounded MISDPs, see this and this and this. This discussed some undecidability of stuff of general non-convex MINLPs, but made no statement about MISDPs or convex MIQP.

So, two questions I guess:

  • Is MISDP decidable? Is there, say, a singly-exponential algorithm for it?
  • And likewise for convex MIQP.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.