Integer Linear Programming

Summary

Integer Linear Programming is a method for:

• optimizing a linear objective function:

maximize $\sum _{i=1}^{m}{c_{i}x_{i}}$

where $c_{i}$ is known and $x_{i}$ is unknown variable

• subject to linear equality or inequality constraints:

$\sum _{i=1}^{m}{a_{i}x_{i}}\leq b_{i}$

where $a_{i}$ and $b_{i}$ are known

• and where $x_{i}$ can only take integer values

In other words, it is a method to find the best assignment of $x_{i}$'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]