Difference between revisions of "Integer Linear Programming"
From Cohen Courses
Jump to navigationJump to search| Line 1: | Line 1: | ||
== Summary == | == Summary == | ||
| − | Integer Linear Programming is a [[category::method]] for | + | Integer Linear Programming is a [[category::method]] for: |
* optimizing a linear objective function: | * 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: | * 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 | + | * and where <math>x_i</math> can only take integer values |
| − | + | In other words, it is a method to find the best assignment of <math>x_i</math>'s that maximizes the objective function while respecting a list of requirements expressed as linear equality or inequality relationships. | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
== Procedure == | == Procedure == | ||
Revision as of 02:32, 28 September 2011
Summary
Integer Linear Programming 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
- and where can only take integer values
In other words, it is a method to find the best assignment of 's that maximizes the objective function while respecting a list of requirements expressed as linear equality or inequality relationships.
Procedure
Input/Definitions:
- D - Original training set
- D_i - One of the bootstrap sample training sets
- n - Size of D
- m - Number of predictors to construct
- M - Set of trained models
- M_i - One of the trained models
Training:
- Generate m new training sets, D_i, of size n_prime < n.
- Do so by sampling from D uniformly and with replacement (a.k.a. a bootstrap sample)
- Train m models, M_i, using bootstrap sample D_i
Output Prediction:
- For Regression: Average outcome of the predictors in M
- For Classification: Vote of the predictors in M
References / Links
- Leo Brieman. Bagging Predictors. Machine Learning, 24, 123–140 (1996). - [1]
- Wikipedia article on Bagging - [2]
