Cutting-plane method

A cutting plane method ( engl. cutting plane algorithm ) is in applied mathematics, an algorithm for solving integer linear programming problems. The basic idea is, instead of an integer linear program (without integrality constraints ) to consider its LP relaxation and to exacerbate inequalities by adding further steps until ( ideally) an integer solution is found.

This, inter alia, of Delbert Ray Fulkerson, George Dantzig, and later by Egon Balas and Ralph Gomory developed in the 1950s method with its developments today one of the standard methods in integer programming and still the subject of current research. As the sole solution method it is usually not sufficient, but provides good dual bounds for optimization problems to be solved. Therefore, it is often combined with branch- and-bound for so-called branch-and -cut method.

Problem definition

A cutting plane method is used to solve integer programs ( engl. integer program, IP) in the normal form

It is a real matrix, and vectors suitable dimension. The condition is component-wise to understand, so as

For all rows of the matrix. Just means the condition that all the entries of the vector must be non-negative.

This can be interpreted geometrically as follows: the amount of

Produced by omitting the integrality forms a convex polyhedron in -dimensional space, the restrictive hyperplanes corresponding to the lines of the inequality system. contains, inter alia, all feasible points of the original system, so all integer points that satisfy the conditions, but in contrast to linear optimization, not all points in admissible. The linear program

Is called the LP relaxation of the integer problem.

The picture to the integer linear program (IP) is

Shown. The permissible integer points are shown in red, and the red dashed lines indicate its convex hull, ie, the smallest polyhedron that contains all these points. About this polyhedron is supposed to be optimized, but it usually is not precisely known. The blue lines together with the coordinate axes define the polyhedra of the LP- relaxation, which is given by the inequality without integrality. The aim of the optimization is to move the black dotted line so far parallel upward ( in the direction of the vector ) that it just touches the respective polyhedron. The optimum solutions of the problem is thus the integral points, and the objective function value. The - in this case unique - optimal solution of the LP relaxation with the objective function value of 2.8 is the blue marked point, which is not an integer, and thus not allowed for the IP.

The basic idea of the algorithm on the example

Cutting plane methods first compute a solution to the LP relaxation. This is usually not an integer (such as the point), but provides an upper (generally dual ) bound for the optimal value of the IP, since any solution of the integer program is also a solution of the LP relaxation and therefore the optimal value of the integer program ( in example 2) can be at most as high as the optimum value of the LP relaxation (in the example 2.8 ). This can be used to estimate the quality of a solution of the IPs.

This dual barrier is then exacerbated by stepwise adding so-called cutting planes. A cross-sectional plane, an additional inequality which is satisfied by all permissible points of the IP, but not from the current LP solution. Is added to the LP inequality, therefore a different solution has to come out when re- solving. This is continued until an integer solution is found ( which automatically also optimal for the integer program is then ) or no suitable inequalities are found.

The picture to the cutting plane (green) is shown, which separates the current LP optimum ( blue) from the IP polyhedron ( separated). All feasible points lie on one side of the hyperplane, the LP solution on the other side. Re- release of the LPs with this additional inequality provides the green marked point (4/3, 7 /3). This point is still not acceptable, but has the smaller objective function value, which improves the upper limit to this value.

The best cutting planes that can be found, are facets of IP - polyhedron, ie -dimensional faces of variables. In the above example these are the inequalities and which correspond to the red dotted lines.

For use in the practice

For a whole range of planning problems, especially those with practical application background (eg, routing problems or assignment problems ), several classes of inequalities are known to be satisfied by all integer points of the polyhedron (that are valid for this polyhedron ). This can be problem- independent IP - sectional planes such as Gomory cuts, which can be found by standard solvers even without knowledge of the practical background, or problem-specific cutting planes that exploit the special structure of the matrix. Examples of the latter are the Kurzzyklusungleichungen the problem of the traveling salesman. Since there are exponentially many Kurzzyklusungleichungen in proportion to the number of nodes of the graph, you can leave them out first, and instead separate gradually.

To find such classes of valid inequalities for certain types or sub-structures of integer programs and to make statements about the quality of these cutting planes is a non-trivial problem. In particular, the information that the conditions under which a cross-sectional plane defining a facet of the polyhedron underlying, usually requires a more detailed mathematical analysis. This is an important subject of current research in integer linear optimization.

Are some classes of valid inequalities is known, the following algorithm is usually applied:

If at the end does not injured sectional plane more found without the LP solution is integral, one can try to heuristically determine an integer solution or to start Branch-and - Bound ( this combination is then called branch-and -cut ). This works in practice, depending on the problem and model used sometimes more and sometimes less.

How the test inequalities in the step ( 3) Injury, depends on the inequalities. In some cases, one can separate the section planes exactly, i.e., if the inequality does not hurt this class, there are none. This is for example the case when a class contains as few inequalities that you simply can by any test. But also in the case of exponentially many Kurzzyklusungleichungen TSP can be tested in polynomial violation by calculating a minimum section in the underlying graph. In other cases, where the separation in a reasonable time is only heuristically possible ( for example, in general Mixed - Integer Rounding Cuts ), is not clear at the end, if there is no injured inequalities more or if you have it just can not be found.

History

The first section planes were mid -1950s by DR Fulkerson, G. Dantzig and P. Johnson developed for the problem of the traveling salesman. Without knowledge of this work and motivated by former colleagues of the U.S. Navy who were interested in integer solutions, R. Gomory developed in 1958 during his stay in Princeton, the first general-purpose cutting plane method. He showed that, theoretically, any integer programs can be solved solely by this method. In practice, this approach has two problems: on the one hand lead many cutting planes eventually to very large linear programs and correspondingly long solution times at each iteration, and on the other hand, often contain proposed by Gomory Schnittungleichungen ( Gomory fractional cuts) many non - zero coefficients, which leads to numerical instability in the solution of the linear program. Nevertheless, This marked a crucial algorithmic progress dar.

In the 1980s, M. Padberg and others were working on cutting planes for frequently appearing substructures such as backpack problems that can often be used in a more general context. In the last ten years, many cutting planes have been discovered for specific application problems, such as routing problems that arise in connection with the planning of public transport networks or in the design of telecommunications networks.