Cutting-plane method

From Wikipedia, the free encyclopedia

In mathematics, more specifically in optimization, the cutting-plane method is a procedure used to find integer solutions of a linear program. It was introduced by Gomory.

It works by solving the non-integer linear program, 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}$

$(2) \,$

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

is a cut or integer formulation of Gomory's cut

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.