Cutting-plane method

From Wikipedia, the free encyclopedia

In mathematics, more specifically in optimization, the cutting-plane method is a method in optimization consisting of polyhedral cutting planes. Such procedures are used to find integer solutions of a linear program, as well as to solve general convex optimization problems. It was introduced by Ralph E. Gomory.

It works by solving the non-integer linear program, the relaxation of the given integer program, and then testing if the optimum found is also an integer solution. If this is not the case, a new restriction is added that cuts off the non-integer solution but does not cut off any integer points of the feasible region. This is repeated until an optimal integer solution is found.

Interpreted geometrically, a restriction is equivalent to an oriented hyperplane, allowing only solutions on one side of the plane.

[edit] Gomory's cut

We have an admissible solution x and we have a base B associated to x that

$\begin{bmatrix}B & F \end{bmatrix}\begin{bmatrix}x_b \\ x_f \end{bmatrix}=b \Rightarrow Bx_b+Fx_f =b\Rightarrow$

$\Rightarrow x_b=B^{-1}b-B^{-1}Fx_f=\bar b\ - \bar A\ x_f \Rightarrow x_b+ \bar A\ x_f= \bar b\$

If we have a fractional solution so we have a nth element of fractionated x .

$(1)\,$

$x_n + \sum_{j \in\ \zeta\ }^N \bar a_{n,j}x_j= \bar b_n$

$\begin{bmatrix} \\ x_b \\ \\ \end{bmatrix} + \begin{bmatrix} & &\\ & \bar A\ & \\ & &\end{bmatrix} \begin{bmatrix} x_f \end{bmatrix} = \begin{bmatrix} \\ \bar b\ \\ \\ \end{bmatrix}$

Since $x_i \geq 0 \; \forall i$ it holds for every solution:

$x_n + \sum_{j \in\ \zeta\ }^N \left \lfloor \bar a_{n,j} \right \rfloor x_j \le \; \bar b_n$

To cut out the current optimal fractional solution without losing integer solutions we round the right hand side to the next smaller integer:

$(2) \,$

$x_n + \sum_{j \in\ \zeta\ }^N \left \lfloor \bar a_{n,j} \right \rfloor x_j \le \; \left \lfloor \bar b_n \right \rfloor$

Substracting $(2)$ from $(1)$ yields the following cut or integer formulation of Gomory's cut:

$(3)\,$

$\sum_{j \in\ \zeta\ }^N \left (\bar a_{n,j}- \left \lfloor \bar a_{n,j} \right \rfloor \right ) x_j \geq \bar b_n - \left \lfloor \bar b_n \right \rfloor$

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.