Integer Linear Programming

Summary

Integer Linear Programming (ILP) is a method for optimizing a linear objective function such as:

maximize $\sum _{i=1}^{m}{c_{i}x_{i}}$

where $c_{i}$ is known and $x_{i}$ is unknown variable, subject to linear equality or inequality constraints such as:

$\sum _{i=1}^{m}{a_{i}x_{i}}\leq b_{i}$

where $a_{i}$ and $b_{i}$ are known, and where $x_{i}$ can only take integer values

In other words, it is a method to find the optimal solution (i.e. the best assignment of unknown variables such as $x_{i}$'s) that maximizes the objective function while meeting a list of requirements expressed as linear equality or inequality relationships.

The strength of ILP is in its joint inference. Instead of making local, isolated assignment of each $x_{i}$, it makes joint assignments of all $x_{i}$'s at the same time; respecting the global constraints while optimizing the objective function given.

ILP is known to be NP-hard. However, there are many off-the-shelf solvers, both commercial and non commercial, that are available. One such solver is SCIP, which is currently the fastest non commercial mixed integer programming solver.

Procedure

Input:

• The linear objective function
• The linear constraints

Output:

• The assignment of unknown variables that optimizes the objective function and is consistent with the constraints

References / Links

• Nemhauser, G.L. and Wolsey, L.A. Integer and combinatorial optimization, 18 (1988). - [1]
• Wikipedia article on Integer Programming - [2]