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:
“This man was very clever and quick to learn anything in his line. Our tent was of a kind new to him; but when he had once seen it pitched, it was surprising how quickly he would find and prepare the pole and forked stakes to pitch it with, cutting and placing them right the first time, though I am sure that the majority of white men would have blundered several times.”
—Henry David Thoreau (1817–1862)
“Have you ever been up in your plane at night, alone, somewhere, 20,000 feet above the ocean?... Did you ever hear music up there?... It’s the music a man’s spirit sings to his heart, when the earth’s far away and there isn’t any more fear. It’s the high, fine, beautiful sound of an earth-bound creature who grew wings and flew up high and looked straight into the face of the future. And caught, just for an instant, the unbelievable vision of a free man in a free world.”
—Dalton Trumbo (1905–1976)
“Frankly, I adore your catchy slogan, “Adoption, not Abortion,” although no one has been able to figure out, even with expert counseling, how to use adoption as a method of birth control, or at what time of the month it is most effective.”
—Barbara Ehrenreich (b. 1941)