Difference between revisions of "Integer Linear Programming"
| Line 1: | Line 1: | ||
== Summary == | == Summary == | ||
| − | Integer Linear Programming (ILP) is a [[category::method]] for | + | Integer Linear Programming (ILP) is a [[category::method]] for ptimizing a linear objective function: |
| − | |||
| − | |||
:: 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> is known and <math>x_i</math> is unknown variable | + | : (where <math>c_i</math> is known and <math>x_i</math> is unknown variable) |
| − | + | subject to linear equality or inequality constraints: | |
:: <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 | + | : (where <math>a_i</math> and <math>b_i</math> are known) |
| − | + | and where <math>x_i</math> 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 21:52, 28 September 2011
Summary
Integer Linear Programming (ILP) is a method for ptimizing a linear objective function:
- maximize
- (where is known and is unknown variable)
subject to linear equality or inequality constraints:
- (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
- Wikipedia article on Integer Programming - [1]
