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}$'s are known and $x_{i}$'s are unknown, subject to linear equality or inequality constraints such as:

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

where $a_{i}$'s and $b_{i}$'s are known, and where $x_{i}$'s 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

Related Methods

ILP method to do joint inference is related to other methods such as Markov Logic Networks.

References / Links

• Nemhauser, G.L. and Wolsey, L.A. Integer and combinatorial optimization, Volume 18, Wiley New York, 1988. - [1]
• Wikipedia article on Integer Programming - [2]