Difference between revisions of "Integer Linear Programming"
| Line 5: | Line 5: | ||
:: maximize <math> \sum_{i=1}^m{c_i x_i} </math> | :: maximize <math> \sum_{i=1}^m{c_i x_i} </math> | ||
| − | where <math>c_i</math> | + | where <math>c_i</math>'s are known and <math>x_i</math>'s are unknown, subject to linear equality or inequality constraints such as: |
:: <math> \sum_{i=1}^m{a_i x_i} \le b_i</math> | :: <math> \sum_{i=1}^m{a_i x_i} \le b_i</math> | ||
| − | where <math>a_i</math> and <math>b_i</math> are known, and where <math>x_i</math> can only take integer values | + | where <math>a_i</math>'s and <math>b_i</math>'s are known, and where <math>x_i</math>'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 <math>x_i</math>'s) that maximizes the objective function while meeting a list of requirements expressed as linear equality or inequality relationships. | In other words, it is a method to find the optimal solution (i.e. the best assignment of unknown variables such as <math>x_i</math>'s) that maximizes the objective function while meeting a list of requirements expressed as linear equality or inequality relationships. | ||
Revision as of 22:00, 28 September 2011
Summary
Integer Linear Programming (ILP) is a method for optimizing a linear objective function such as:
- maximize
where 's are known and 's are unknown, subject to linear equality or inequality constraints such as:
where 's and 's are known, and where '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 '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]
