2
$\begingroup$

I have recently been working on an applied project where I have to solve optimization problems.

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.

I am wondering if there is some kind of formal result that confirms this (i.e. on the time complexity of ILP vs. MILP).

To be clear, when I am refering to an ILP I mean an optimization problem of the form

$$\begin{align} \min_{x} \quad & c^Tx \\ \text{s.t.} \quad & Ax = b \\ \; & x\in\mathbb{Z}^N\end{align}$$

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.

$\endgroup$
  • $\begingroup$ Computational complexity probably won't help you here: Both problems are NP-complete. $\endgroup$ – DCTLib Sep 15 '14 at 10:15
2
$\begingroup$

Knowing that integer programming (ILP) is NP-complete, it follows that mixed integer linear programming (MILP) is NP-complete too as MILP generalizes ILP.

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.

$\endgroup$

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.