Integer Linear Programming

From Cohen Courses
Jump to navigationJump to search

Summary

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

maximize

where is known and is unknown variable, subject to linear equality or inequality constraints such as:

where and are known, and where 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 '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 , it makes joint assignments of all '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]

Relevant Papers