15.053 Lecture Notes - Lecture 12: Integer Programming, Linear Programming
Document Summary
Lecture 12: cutting planes and the geometry of integer programs. There are often many ways of writing an integer program. Some have linear program relaxations that give better bounds than others. Fundamental idea of this lecture x + 2y. 3x + 4y 5 x {0, 1}, y {0, 1) Select an integer program formulation such that z is very close to z. Sometimes the way to improve the integer program formulation is obvious. Integer program: max z = 3x + 4y. Linear program: max z = 3x + 4y. 5x + 8y 24 x, y 0. Valid inequality: a constraint is valid for an integer program if adding the constrain to the integer program does not change the feasible region of the integer program. A cut: a cut is a valid inequality with the additional property that the feasible region for the linear program relaxation is smaller after adding the cut.
