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$
1
  • $\begingroup$ Computational complexity probably won't help you here: Both problems are NP-complete. $\endgroup$
    – DCTLib
    Sep 15, 2014 at 10:15

3 Answers 3

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$
0
$\begingroup$

Mixed-integer linear programming (MILP) is at least as hard as Integer linear programming (ILP), so this is already a theoretical justification for ILP being easier to solve. Both are NP-hard, but NP-hardness is often a rather blunt sword, especially when it comes to practical behaviour (see for example the enormous practical success of the Concorde solver for the NP-hard TSP problem). If you look at a more fine-grained classification, you also find that there are fixed-parameter tractable algorithms for ILP (which have a polynomial worst-case run time if certain input parameters of the ILP are fixed), such as the LLL algorithm, see https://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz_lattice_basis_reduction_algorithm.

There are also many empirically successful algorithms that are used in modern MILP solvers (such as SCIP) that get stronger the more integer variables you have.

$\endgroup$
0
$\begingroup$

With usual linear programming, you can find an optimal solution in a reasonably straightforward way. Any variable that has a different condition attached to it adds difficulty. So usually it’s the number of integer variables that add complications. Integer variables with strong restrictions may be easier to remove completely.

(Other restrictions: x might be restricted to x= 0 or x>= 20, for example. )

$\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.