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?
$\begingroup$
$\endgroup$
0
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
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.
answered Nov 12, 2019 at 15:33
-
2$\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$ Nov 24, 2019 at 14:26
-
$\begingroup$ Is there any book or paper for those claims that can be cited and verified? Thank you. $\endgroup$ Aug 6, 2022 at 12:55
$\begingroup$
$\endgroup$
2
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.
answered Nov 12, 2019 at 8:02
-
$\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$ Nov 24, 2019 at 14:58
-
1$\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$ Nov 24, 2019 at 14:58