Cutting-Plane

Cutting-plane method

The cutting-plane method was developed by Schrijver, it is intended to solve combinatorial optimization (POC) problems which are formulated in the form of a linear program (PL):

cutting-plane

In the case, where the POC is large to represent it explicitly in memory or so that it fits in a linear programming solver, a technique is used which consists in removing some of these constraints and solving the relaxed problem ( POCR). The optimal solution of (PL) is contained in the set of feasible solutions of this relaxation. For a minimization problem the optimal solution of the problem (POCR) is less than or equal to the optimal solution given by (POC)

cutting-plane

This method consists in solving a relaxed problem, and in iteratively adding constraints to the initial problem. We define a constraint for the problem of minimization by the couple (s, s0) where s is in Rnot and s0 in R, this constraint is said to be violated by the current solution x (bar) if for all:

These constraints are then called plane sections. One stops the algorithm when there are no more constraints violated by the current solution, one thus obtains an optimal solution for the initial problem.

The flat section method is not very efficient but its performance is improved when it is combined with the Branch and Bound method.

To share
en_GBEN
%d bloggers like this: