12

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!

Tobia Marcucci
  • 275
  • 1
  • 7
  • 3
    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. – Marco Lübbecke Jul 30 '19 at 19:29

1 Answers1

13

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.

Austin Buchanan
  • 606
  • 6
  • 13