Difference between revisions of "Integer Linear Programming"
From Cohen Courses
Jump to navigationJump to search| Line 3: | Line 3: | ||
Integer Linear Programming (ILP) is a [[category::method]] for: | Integer Linear Programming (ILP) is a [[category::method]] for: | ||
| − | * | + | * Optimizing 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 | ||
| − | * | + | * 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. | ||
| − | The strength of ILP is in its joint inference. Instead of making local, isolated | + | 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; guided by global constraints and 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 01:54, 28 September 2011
Summary
Integer Linear Programming (ILP) is a method for:
- Optimizing a linear objective function:
- maximize
- where is known and is unknown variable
- Subject to linear equality or inequality constraints:
- where and are known
- 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; guided by global constraints and 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
- Leo Brieman. Bagging Predictors. Machine Learning, 24, 123–140 (1996). - [1]
- Wikipedia article on Bagging - [2]
