Cutting Plane Method
Two 0-1 integer programs that are equivalent, in that they have the same objective function and the same set of feasible solutions, may have quite different linear programming relaxations: a linear programming relaxation can be viewed geometrically, as a convex polytope that includes all feasible solutions and excludes all other 0-1 vectors, and infinitely many different polytopes have this property. Ideally, one would like to use as a relaxation the convex hull of the feasible solutions; linear programming on this polytope would automatically yield the correct solution to the original integer program. However, in general, this polytope will have exponentially many facets and be difficult to construct. Typical relaxations, such as the relaxation of the set cover problem discussed earlier, form a polytope that strictly contains the convex hull and has vertices other than the 0-1 vectors that solve the unrelaxed problem.
The cutting-plane method for solving 0-1 integer programs, first introduced for the traveling salesman problem by Dantzig, Fulkerson & Johnson (1954) and generalized to other integer programs by Gomory (1958), takes advantage of this multiplicity of possible relaxations by finding a sequence of relaxations that more tightly constrain the solution space until eventually an integer solution is obtained. This method starts from any relaxation of the given program, and finds an optimal solution using a linear programming solver. If the solution assigns integer values to all variables, it is also the optimal solution to the unrelaxed problem. Otherwise, an additional linear constraint (a cutting plane or cut) is found that separates the resulting fractional solution from the convex hull of the integer solutions, and the method repeats on this new more tightly constrained problem.
Problem-specific methods are needed to find the cuts used by this method. It is especially desirable to find cutting planes that form facets of the convex hull of the integer solutions, as these planes are the ones that most tightly constrain the solution space; there always exists a cutting plane of this type that separates any fractional solution from the integer solutions. Much research has been performed on methods for finding these facets for different types of combinatorial optimization problems, under the framework of polyhedral combinatorics (Aardal & Weismantel 1997).
The related branch and cut method combines the cutting plane and branch and bound methods. In any subproblem, it runs the cutting plane method until no more cutting planes can be found, and then branches on one of the remaining fractional variables.
Read more about this topic: Linear Programming Relaxation
Famous quotes containing the words cutting, plane and/or method:
“I feel no more like a man now than I did in long skirts, unless it be that enjoying more freedom and cutting off the fetters is to be like a man. I suppose in that respect we are more mannish, for we know that in dress, as in all things else, we have been and are slaves, while man in dress and all things else is free.”
—Amelia Bloomer (1818–1894)
“with the plane nowhere and her body taking by the throat
The undying cry of the void falling living beginning to be something
That no one has ever been and lived through screaming without enough air”
—James Dickey (b. 1923)
“I have a new method of poetry. All you got to do is look over your notebooks ... or lay down on a couch, and think of anything that comes into your head, especially the miseries.... Then arrange in lines of two, three or four words each, don’t bother about sentences, in sections of two, three or four lines each.”
—Allen Ginsberg (b. 1926)