10
$\begingroup$

The pieces of information I get online are sometimes confusing. Someone says MILP problems are NP-hard, and somewhere else I found the claim that MILP problems are NP-complete. Can someone please clarify it?

$\endgroup$
14
$\begingroup$

For an introduction to complexity theory, see this answer.

A problem is NP-complete if it is both in NP and it is NP-hard. Only decision problems are in NP. Hence, if one considers MILP as a decision or feasibility problem, it is correct to say that MILP is NP-complete as well as NP-hard. Maximization and minimization problems are not decision problems (although they can easily be transformed into decision problems), so if one considers MILP as an optimization problem, MILP is not NP-complete but is NP-hard.

$\endgroup$
  • 1
    $\begingroup$ It might be good to add that while the decision variant of MILP lies in NP, the proof of this is not easy (at the least, proving MILP is NP-hard is a lot easier). Although an optimal point would work as a certificate, the tricky part is to show that we can always find an optimal point that can be encoded in polynomial size. (For a proof of the latter, see e.g. Section 4.8.2 of the book Integer programming by Conforti, Cornuéjols, Zambelli) $\endgroup$ – Discrete lizard Nov 24 '19 at 14:26
3
$\begingroup$

A very good discussion of the complexity of MILP is given in the paper1 and the reference within2. Based on the discussion in section $3.2$ MILP is NP-hard.

(1) Bulut, Aykut, and Ted K. Ralphs. On the complexity of inverse mixed integer linear optimization. Tech. rep. COR@ L Laboratory Report 15T-001-R3, Lehigh University, 2015 (cit. on p. 147).

(2) Papadimitriou, Christos H., and Mihalis Yannakakis. "The complexity of facets (and some facets of complexity)." Journal of Computer and System Sciences 28.2 (1984): 244-259.

$\endgroup$
  • $\begingroup$ While section 3.2 of (1) raises a valid point that there are multiple decision problems related to MILP, I'm not sure how useful these references are wrt. the question of whether MILP is NP-complete. (1) claims that "In the case of MILPD, the short certificate is any feasible solution." (emphasis mine), but this is false: the feasible region can contain a non-trivial segment, which will always contain some point that cannot be encoded in polynomial size. It is nessecary to show there always exists a solution with a short certificate. $\endgroup$ – Discrete lizard Nov 24 '19 at 14:58
  • $\begingroup$ (2) considers a variant that is usually not considered to be "the" decision variant of MILP, and considers membership and hardness wrt $D^p$, which doesn't tell us whether this variant of MILP lies in NP. Can you clarify why you think this paper is relevant here? $\endgroup$ – Discrete lizard Nov 24 '19 at 14:58

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.