Difference between revisions of "Integer Linear Programming"
From Cohen Courses
Jump to navigationJump to searchLine 13: | Line 13: | ||
* 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 | + | In other words, it is a method to find the best assignment of <math>x_i</math>'s that maximizes the objective function while meeting a list of requirements expressed as linear equality or inequality relationships. |
== Procedure == | == Procedure == |
Revision as of 01:34, 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 meeting 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]