Cutting-plane method

In mathematical optimization, the cutting-plane method is any of a variety of optimization methods that iteratively refine a feasible set or objective function by means of linear inequalities, termed cuts.

Such procedures are commonly 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.

The theory of Linear Programming dictates that under mild assumptions (if the linear program has an optimal solution, and if the feasible region does not contain a line), one can always find an extreme point or a corner point that is optimal.

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.

Then, the current non-integer solution is no longer feasible to the relaxation.

This process is repeated until an optimal integer solution is found.

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.

However, 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 Gérard Cornuéjols and co-workers showed them to be very effective in combination with branch-and-bound (called branch-and-cut) and ways to overcome numerical instabilities.

Nowadays, all commercial MILP solvers use Gomory cuts in one way or another.

[1][2] Let an integer programming problem be formulated (in canonical form) as: where A is a matrix and b , c is a vector.

The vector x is unknown and is to be found in order to maximize the objective while respecting the linear constraints.

The method proceeds by first dropping the requirement that the xi be integers and solving the associated relaxed linear programming problem to obtain a basic feasible solution.

Geometrically, this solution will be a vertex of the convex polytope consisting of all feasible points.

The new program is then solved and the process is repeated until an integer solution is found.

Using the simplex method to solve a linear program produces a set of equations of the form where xi is a basic variable and the xj's are the nonbasic variables (i.e. the basic solution which is an optimal solution to the relaxed linear program is

with a bar to denote the last tableau produced by the simplex method.

So the inequality must hold for any integer point in the feasible region.

is negative for any integer point in the feasible region, and strictly positive for the basic feasible (non integer) solution of the relaxed linear program.

Introducing a new slack variable xk for this inequality, a new constraint is added to the linear program, namely 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.

The intersection of the unit cube with the cutting plane . In the context of the Traveling salesman problem on three nodes, this (rather weak [ why? ] ) inequality states that every tour must have at least two edges.
Graph of a strictly concave quadratic function with unique maximum.
Optimization computes maxima and minima.