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:
“For universal love is as special an aspect as carnal love or any of the other kinds: all forms of mental and spiritual activity must be practiced and encouraged equally if the whole affair is to prosper. There is no cutting corners where the life of the soul is concerned....”
—John Ashbery (b. 1927)
“In time the scouring of wind and rain will wear down the ranges and plane off the region until it has the drab monotony of the older deserts. In the meantimea two-million-year meantimetravelers may enjoy the cruel beauties of a desert in its youth,....”
—For the State of California, U.S. public relief program (1935-1943)
“... [a] girl one day flared out and told the principal the only mission opening before a girl in his school was to marry one of those candidates [for the ministry]. He said he didnt know but it was. And when at last that same girl announced her desire and intention to go to college it was received with about the same incredulity and dismay as if a brass button on one of those candidates coats had propounded a new method for squaring the circle or trisecting the arc.”
—Anna Julia Cooper (18591964)