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:
“The sole work and deed of universal freedom is therefore death, a death too which has no inner significance or filling, for what is negated is the empty point of the absolutely free self. It is thus the coldest and meanest of all deaths, with no more significance than cutting off a head of cabbage or swallowing a mouthful of water.”
—Georg Wilhelm Friedrich Hegel (1770–1831)
“Even though I had let them choose their own socks since babyhood, I was only beginning to learn to trust their adult judgment.. . . I had a sensation very much like the moment in an airplane when you realize that even if you stop holding the plane up by gripping the arms of your seat until your knuckles show white, the plane will stay up by itself. . . . To detach myself from my children . . . I had to achieve a condition which might be called loving objectivity.”
—Anonymous Parent of Adult Children. Ourselves and Our Children, by Boston Women’s Health Book Collective, ch. 5 (1978)
“As a science of the unconscious it is a therapeutic method, in the grand style, a method overarching the individual case. Call this, if you choose, a poet’s utopia.”
—Thomas Mann (1875–1955)