Cutting-plane method
From Wikipedia, the free encyclopedia
In mathematical optimization, the cutting-plane method is an umbrella term for optimization methods which iteratively refine a feasible set or objective function by means of linear inequalities, termed cuts. Such procedures are popularly used to find integer solutions to mixed integer linear programming (MILP) problems, as well as to solve general, not necessarily differentiable convex optimization problems. The use of cutting planes to solve MILP was introduced by Ralph E. Gomory.
Cutting plane methods for MILP work by solving a non-integer linear program, the linear relaxation of the given integer program. The obtained optimum is tested for being an integer solution. If it is not, there is guaranteed to exist a linear inequality that separates the optimum from the convex hull of the true feasible set. Finding such an inequality is the separation problem, and such an inequality is a cut. A cut can be added to the relaxed linear program to cut off the current non-integer solution. This process is repeated until an optimal integer solution is found.
Cutting-plane methods for general convex continuous optimization and variants are known under various names: Kelley's method, Kelley-Cheney-Goldstein method, and bundle methods. They are popularly used for non-differentiable convex minimization, where a convex objective function and its subgradient can be evaluated efficiently but usual gradient methods for differentiable optimization can not be used. This situation is most typical for the concave maximization of Lagrangian dual functions. Another common situation is the application of the Dantzig-Wolfe decomposition to a structured optimization problem in which formulations with an exponential number of variables are obtained. Generating these variables on demand by means of delayed column generation is identical to performing a cutting plane on the respective dual problem.
Contents |
[edit] Gomory's cut
We have an admissible solution x and we have a base B associated to x that
If we have a fractional solution so we have a nth element of fractionated x .
Since 
it holds for every solution:
To cut out the current optimal fractional solution without losing integer solutions we round the right hand side to the next smaller integer:
Subtracting (2) from (1) yields the following cut or integer formulation of Gomory's cut:
Although Gomory's cuts were proposed in the 60s, they were forgotten for almost thirty years; most experts, including Gomory himself, considered them to be impractical due to numerical instability, as well as ineffective because many rounds of cuts were needed to make progress towards the solution. Things turned around when in the mid-1990s Cornuejols and co-workers showed them to be very effective in combination with branch-and-cut and ways to overcome numerical instabilities. Nowadays, all commercial MILP solvers use Gomory cuts in one way or another.
More general cuts are known for mixed integer programs. Gomory cuts, however, are very efficiently generated from a simplex tableau, whereas many other types of cuts are either expensive or even NP-hard to separate. Among other general cuts for MILP, most notably lift-and-project dominates Gomory cuts.
[edit] Convex optimization
Cutting plane methods are also applicable in nonlinear programming. The underlying principle is to approximate the feasible region of a nonlinear (convex) program by a finite set of closed half spaces and to solve a sequence of approximating linear programs.
[edit] References
Avriel, Mordecai (2003). Nonlinear Programming: Analysis and Methods. Dover Publications. ISBN 0-486-43227-0
Cornuejols, Gerard (2008). Valid Inequalities for Mixed Integer Linear Programs. Mathematical Programming, to appear. [1]
Cornuejols, Gerard (2007). Revival of the Gomory Cuts in the 1990s. Annals of Operations Research, Vol. 149 (2007), pp. 63-66. [2]
