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!

Improve this question
$\endgroup$
1
  • 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, 2019 at 19:29

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

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.