Integer Linear Programming

Summary

Integer Linear Programming (ILP) 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 optimal solution (i.e. the best assignment of unknown variables such as $x_{i}$'s) that maximizes the objective function while meeting a list of requirements expressed as linear equality or inequality relationships.

Procedure

Input/Definitions:

• the objective function
• the constraints

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]