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. 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.…

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. 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. x_i+\sum_j \bar a_{i,j}x_j=\bar b_i where x_i is a basic variable and the x_j 's are the nonbasic variables (i.e. the basic solution which is an optimal solution to the relaxed linear program is x_i=\bar b_i and x_j=0 ). We write coefficients \bar b_i and \bar a_{i,j} with a bar to denote the last tableau produced by the simplex method. These coefficients are different from the coefficients in the matrix A and the vector b . x_i+\sum_j \lfloor \bar a_{i,j} \rfloor x_j - \lfloor \bar b_i \rfloor = \bar b_i - \lfloor \bar b_i \rfloor - \sum_j ( \bar a_{i,j} -\lfloor \bar a_{i,j} \rfloor) x_j. For any integer point in the feasible region, the left side is an integer since all the terms x_i , x_j , \lfloor \bar a_{i,j} \rfloor , \lfloor \bar b_i \rfloor are integers. The right side of this equation is strictly less than 1: indeed, \bar b_i - \lfloor \bar b_i \rfloor is strictly less than 1 while - \sum_j ( \bar a_{i,j} -\lfloor \bar a_{i,j} \rfloor) x_j is negative. Therefore the common value must be less than or equal to 0. So the inequality \bar b_i - \lfloor \bar b_i \rfloor - \sum_j ( \bar a_{i,j} -\lfloor \bar a_{i,j} \rfloor) x_j \le 0 must hold for any integer point in the feasible region. Furthermore, non-basic variables are equal to 0s in any basic solution and if x i is not an integer for the basic solution x, \bar b_i - \lfloor \bar b_i \rfloor - \sum_j ( \bar a_{i,j} -\lfloor \bar a_{i,j} \rfloor) x_j = \bar b_i - \lfloor \bar b_i \rfloor > 0. x_k + \sum_j (\lfloor \bar a_{i,j} \rfloor - \bar a_{i,j}) x_j = \lfloor \bar b_i \rfloor - \bar b_i,\, x_k \ge 0,\, x_k \mbox{ an integer}.

External links

"Integer Programming" Section 9.8 Applied Mathematical Programming Chapter 9 Integer Programming (full text). Bradley, Hax, and Magnanti (Addison-Wesley, 1977) "Generating Gomory's Cuts for linear integer programming problems: the HOW and WHY" Generating Gomory's Cuts for linear integer programming problems: the HOW and WHY

Text derived from https://en.wikipedia.org/w/index.php?oldid=1378613967 under CC BY-SA 4.0; modifications have been made.