Integer Linear Programming

Summary

Integer Linear Programming (ILP) is a method for:

• Optimizing a linear objective function:

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:

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

where $a_{i}$ and $b_{i}$ are known

• 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

• Wikipedia article on Integer Programming - [1]