Integer Linear Programming
From Cohen Courses
Jump to navigationJump to searchSummary
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]