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.

Improve this question
$\endgroup$
1
  • $\begingroup$ Computational complexity probably won't help you here: Both problems are NP-complete. $\endgroup$
    – DCTLib
    Commented Sep 15, 2014 at 10:15

3 Answers 3

Reset to default
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.

Improve this answer
$\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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Ten non-integer conditions plus 20 integer conditions are harder than 20 integer conditions. But you'd need comparable problems. 30 integer conditions is also usually more difficult than 20. $\endgroup$
    – gnasher729
    Commented Nov 8, 2022 at 8:47
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. )

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.