Difficulty of Integer Linear Programming vs. Mixed Integer Linear Programming - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-08-22T07:17:14Z https://cs.stackexchange.com/feeds/question/30009 http://www.creativecommons.org/licenses/by-sa/3.0/rdf https://cs.stackexchange.com/q/30009 2 Difficulty of Integer Linear Programming vs. Mixed Integer Linear Programming Berk U. https://cs.stackexchange.com/users/2046 2014-09-15T04:35:55Z 2015-04-22T10:40:19Z <p>I have recently been working on an applied project where I have to solve optimization problems. </p> <p>I have found that it is much easier to solve an integer linear program (ILP) as opposed to a mixed-integer linear programs (MILP), in the sense it is faster for me to find feasible solutions as well as to prove optimality.</p> <p>I am wondering if there is some kind of formal result that confirms this (i.e. on the time complexity of ILP vs. MILP). </p> <p>To be clear, when I am refering to an ILP I mean an optimization problem of the form</p> <p>\begin{align} \min_{x} \quad &amp; c^Tx \\ \text{s.t.} \quad &amp; Ax = b \\ \; &amp; x\in\mathbb{Z}^N\end{align}</p> <p>where the variables are integer-valued so that $x\in\mathbb{Z}^N$ but the parameters are real valued so that $c \in \mathbb{R}^N$, $A \in \mathbb{R}^{M \times N}$, $b \in \mathbb{R}^M$. In turn, an MILP would be different in that at least one of the variables would take on a real value.</p> https://cs.stackexchange.com/questions/30009/-/41696#41696 2 Answer by Juho for Difficulty of Integer Linear Programming vs. Mixed Integer Linear Programming Juho https://cs.stackexchange.com/users/472 2015-04-22T10:40:19Z 2015-04-22T10:40:19Z <p>Knowing that integer programming (ILP) is NP-complete, it follows that mixed integer linear programming (MILP) is NP-complete too as MILP generalizes ILP.</p> <p>My guess is that your thinking and feeling comes from insufficient testing: you don't have enough test cases with different structure, and you don't mention what algorithms you use. Even though both problems are hard, there are (even exact) algorithms that perform well on suitably structured instances. You should look at where the really hard instances are (they are not necessarily large), and try running your algorithms again.</p>