Integer Linear Programming

From Cohen Courses
Revision as of 01:50, 28 September 2011 by Dwijaya (talk | contribs)
Jump to navigationJump to search

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
  • and 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.

Integer Linear Programming 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]

Relevant Papers