12
$\begingroup$

I looked around for a while, but I couldn't find a precise answer to the following question.

If I'm given a candidate solution for a (mixed) integer (convex) program, what's the complexity of deciding whether this solution (a point in the decision space) is optimal or not? I imagine that this decision problem is not NP (i.e., optimality of a MIP feasible solution can't be certified in polynomial time), right? Do you know any text or a reference where this problem is treated in detail?

Thank you very much!

$\endgroup$
  • 3
    $\begingroup$ not sure if you don't give the answer yourself: MIP optimality can't be certified in polytime; otherwise you could decide a lot of (=all) NP-complete decision problems in polytime. $\endgroup$ – Marco Lübbecke Jul 30 at 19:29
13
$\begingroup$

Deciding if a given solution to a mixed integer linear program is optimal is coNP-complete.

When the answer is “no, it is not optimal” there is an efficiently verifiable witness—a better solution.

Minor caveat: This answer assumes that there is a better solution that is efficiently verifiable (which necessitates that it can be represented with a polynomial number of bits). This is true for mixed integer linear programs, but might not be true for a more generic mixed integer convex program. Here is a recent paper on the issue of polynomial-size bit encodings for mixed integer quadratic programs.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.