Cutting-plane method

The cutting-plane method was developed by Schrijver and is intended to solve combinatorial optimization problems (COP) that are formulated as a linear program (LP):
cuttingplane
In the case where the COP is large enough to represent it explicitly in memory or to fit into a linear programming solver, a technique is used which consists of removing some of these constraints and solving the relaxed problem (RCOP). The optimal solution of (LP) is contained in the set of feasible solutions of this relaxation. For a problem of minimization the optimal solution of the problem (RCOP) is less than or equal to the optimal solution given by (COP).

This method consists in solving a relaxed problem, and iteratively adding constraints of the initial problem. We define a constraint for the minimization problem by the pair (s,s0) where s is in Rn and s0 in R, this constraint is said to be violated by the current solution x (bar) if for all:
cuttingplane2
These constraints are then called cutting-plane. We stop the algorithm when there are no more constraints violated by the current solution, we thus obtain an optimal solution for the initial problem.

The method of cutting-planes is inefficient but its performance is enhanced when combined with the Branch and Bound method.

 

Publicités