Cutting-plane method
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 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. 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. Then, the current non-integer solution is no longer feasible to the relaxation. 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.
in the 1950s as a method for solving integer programming and mixed-integer programming problems. 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 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. 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.
Let an integer programming problem be formulated as
The method proceeds by first dropping the requirement that the xi be integers and solving the associated 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. If this vertex is not an integer point then the method finds a hyperplane with the vertex on one side and all feasible integer points on the other. This is then added as an additional linear constraint to exclude the vertex found, creating a modified linear programming program. 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 xjs are the nonbasic variables. Rewrite this equation so that the integer parts are on the left side and the fractional parts are on the right side:
For any integer point in the feasible region the right side of the this equation is less than 1 and the left side is an integer, therefore the common value must be less than or equal to 0. So the inequality
must hold for any integer point in the feasible region. Furthermore, if ci is not an integer for the basic solution x,
So the inequality above excludes the basic feasible solution and thus is a cut with the desired properties. Introducing a new slack variable xk for this inequality, a new constraint is added to the linear program, namely
Introduce slack variables xi, i=4, 5, 6 to produce the standard form
Solving this with the simplex method gives the solution x1=x2=x3=1/2 and the equations
Each of these equations produces the same cutting plane, and with the introduction of a new slack variable x7 it can be written as a new constraint
An analysis of the updated linear program quickly shows that the original three constraints are now redundant and the corresponding slack variables can be eliminated, leaving the simplified problem
This is easily solved giving three solutions (x1, x2, x3) = (1, 0, 0), (0, 1, 0), or (0, 0, 1).
. 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.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
optimization
Optimization (mathematics)
In mathematics, computational science, or management science, mathematical optimization refers to the selection of a best element from some set of available alternatives....
, 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
Integer
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
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
Ralph E. Gomory
Ralph Edward Gomory is an American applied mathematician and executive. Gomory worked at IBM as a researcher and later as an executive. During that time, his research led to the creation of new areas of applied mathematics....
.
Cutting plane methods for MILP work by solving a non-integer linear program, the linear relaxation of the given integer program. 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. The obtained optimum
Optimization (mathematics)
In mathematics, computational science, or management science, mathematical optimization refers to the selection of a best element from some set of available alternatives....
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
Convex hull
In mathematics, the convex hull or convex envelope for a set of points X in a real vector space V is the minimal convex set containing X....
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. Then, the current non-integer solution is no longer feasible to the relaxation. 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
Lagrange multipliers
In mathematical optimization, the method of Lagrange multipliers provides a strategy for finding the maxima and minima of a function subject to constraints.For instance , consider the optimization problem...
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
Delayed column generation
Delayed column generation is an efficient algorithm for solving larger linear programs.The overarching idea is that many linear programs are too large to consider all the variables explicitly. Since most of the variables will be non-basic and assume a value of zero in the optimal solution, only a...
is identical to performing a cutting plane on the respective dual problem.
Gomory's cut
Cutting planes were proposed by R. GomoryRalph E. Gomory
Ralph Edward Gomory is an American applied mathematician and executive. Gomory worked at IBM as a researcher and later as an executive. During that time, his research led to the creation of new areas of applied mathematics....
in the 1950s as a method for solving integer programming and mixed-integer programming problems. 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 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. 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.
Let an integer programming problem be formulated as
The method proceeds by first dropping the requirement that the xi be integers and solving the associated 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. If this vertex is not an integer point then the method finds a hyperplane with the vertex on one side and all feasible integer points on the other. This is then added as an additional linear constraint to exclude the vertex found, creating a modified linear programming program. 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 xjs are the nonbasic variables. Rewrite this equation so that the integer parts are on the left side and the fractional parts are on the right side:
For any integer point in the feasible region the right side of the this equation is less than 1 and the left side is an integer, therefore the common value must be less than or equal to 0. So the inequality
must hold for any integer point in the feasible region. Furthermore, if ci is not an integer for the basic solution x,
So the inequality above excludes the basic feasible solution and thus is a cut with the desired properties. Introducing a new slack variable xk for this inequality, a new constraint is added to the linear program, namely
Example
Consider the integer optimization problem- Maximize
- Subject to
Introduce slack variables xi, i=4, 5, 6 to produce the standard form
- Maximize
- Subject to
Solving this with the simplex method gives the solution x1=x2=x3=1/2 and the equations
Each of these equations produces the same cutting plane, and with the introduction of a new slack variable x7 it can be written as a new constraint
An analysis of the updated linear program quickly shows that the original three constraints are now redundant and the corresponding slack variables can be eliminated, leaving the simplified problem
- Maximize
- Subject to
- xi ≥ 0, xi an integer for i=1, 2, 3, 7.
This is easily solved giving three solutions (x1, x2, x3) = (1, 0, 0), (0, 1, 0), or (0, 0, 1).
Convex optimization
Cutting plane methods are also applicable in nonlinear programmingNonlinear programming
In mathematics, nonlinear programming is the process of solving a system of equalities and inequalities, collectively termed constraints, over a set of unknown real variables, along with an objective function to be maximized or minimized, where some of the constraints or the objective function are...
. 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.
See also
- Branch and cutBranch and cutBranch and cut is a method of combinatorial optimization for solving integer linear programs, that is, linear programming problems where some or all the unknowns are restricted to integer values...
- Branch and boundBranch and boundBranch and bound is a general algorithm for finding optimal solutions of various optimization problems, especially in discrete and combinatorial optimization...
- Dantzig-Wolfe decomposition
- Column generation
- Benders' decompositionBenders' decompositionBenders' decomposition is a technique in mathematical programming that allows the solution of very large linear programming problems that have a special block structure...