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>'s are known and <math>x_i</math>'s are unknown, subject to linear equality or inequality constraints such as: | + | 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>'s and <math>b_i</math>'s are known, and where <math>x_i</math>'s 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> | + | 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>) 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 <math>x_i</math>, it makes joint assignments of all <math>x_i</math>'s at the same time; respecting the global constraints while optimizing the objective function given. | + | The strength of ILP is in its joint inference. Instead of making local, isolated assignment of each <math>x_i\,\!</math>, it makes joint assignments of all <math>x_i\,\!</math>'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 [http://scip.zib.de/ SCIP], which is currently the fastest non commercial mixed integer programming solver. | 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 [http://scip.zib.de/ SCIP], which is currently the fastest non commercial mixed integer programming solver. | ||
Revision as of 00:04, 29 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 ) 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
Related Methods
ILP method to do joint inference is related to other methods such as Markov Logic Networks, a combination of first-order logic and Markov networks, which also incorporates global learning and inference to improve local classifiers' decisions. Global constraints are enforced through the addition of weighted first order logic formulae. The difference with ILP is that Markov Logic Network allows for non-deterministic (soft) constraints. Constraints are assigned different weights during learning phase, thus allowing for constraints that tend to hold but do not always have to. ILP on the other hand enforces hard constraints. It is possible to incorporate weighted constraints into ILPs, however it is not obvious how the weights should be learnt.
Another related method to do joint inference is a version of Path Ranking Algorithm that conducts soft inference based on a combination of constrained, weighted, random walks through a network of local decisions and their relations.
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]
