Branch-and-Cut

Branch - and-cut or branch and section referred to combinatorial optimization, a branch of discrete mathematics, a method for solving integer linear programming problems. The method consists of a combination of cutting-plane method and branch -and-bound.

History

While cutting planes and branch -and-bound have been developed in the 1950s and 1960s, these methods were combined only in the 1980s to branch-and -cut. One of the first applications of this method was the study of the problem of the traveling salesman by Manfred Padberg, Martin Grötschel, and others who have contributed significantly to the development of branch-and -cut. In the 1990s better Branchingregeln and clever combinations of both procedures were George Nemhauser, Laurence Wolsey, Robert Bixby and other new cutting planes for different combinatorial optimization problems developed, whereby branch-and -cut is now become a standard tool in integer linear optimization. The best solver for integer linear programs today are based on this principle, and the solution methods are developed further still.

The basic idea

The aim of the integer linear optimization is to maximize ( or minimize ) a linear objective function over a polyhedron, which is given by a linear inequality, wherein only integral points are allowed:

This problem is NP-complete in general terms, that is, it is probably not be solved efficiently. A standard approach to the integer linear optimization is to solve the so-called LP relaxation of this system, ie the linear program, which is formed by omitting the integrality constraints. This problem is relatively easy to solve, such as the simplex method.

Cutting plane method

Although the solution of the LP relaxation satisfies the conditions, but is not an integer in general. A cutting plane method now adds the system further inequalities which will be met by all permissible ( integer ) points, but not from the current solution of the LP relaxation. When re- solving the system with the new inequalities therefore a different solution has to come out, which is hopefully " closer" to the desired optimum. If the new solution is an integer, it is also optimal for the original problem. Otherwise, must be searched again for new cutting planes. Geometrically, adding another inequality of determining an hyperplane (pictured green) that separates the LP solution ( blue dot at the top) from the mostly unknown polyhedron of integer points (red).

Branch-and - Bound

If no further cutting planes found more that one might add, without the current solution is an integer, a branch- and-bound process is started. This divides the problem into two subproblems. A standard method is the branching on a single variable. For example, if a variable that should be an integer actually, in the current LP solution in a subproblem the value 1.8, then this variable is set to limited and in the other (see picture ). Thus, the set of feasible solutions into two disjoint, ie non-overlapping parts is divided because every feasible solution must satisfy exactly one of the two conditions, yes. Instead barriers to rely on individual variables, more linear inequalities can be added in any part of problem.

By iterative application of this method, a decision tree is constructed in which a part of the problem is even further limited, the lower it is in the tree. In this way, the entire solution space can be systematically searched. An advantage of this method over the pure enumeration of all solutions is the fact that in some cases complete subtrees can be cut off ( bounding ), because it is clear that in this subtree no optimal solution can be contained.

Combination with branch-and -cut

Due to the fact that prior to the Branch - and-bound process already cutting planes are added to the LP relaxation, the process is often much quicker solution than if the branch- and-bound tree is built on the original LP relaxation. In addition, further cutting planes can be determined frequently during the Branchings that could have been without the limitations not found in the sub-problems. These cutting planes can either globally valid, ie valid for the original problem, or locally valid, so be admissible only to the current subtree with its limitations. Furthermore, additional heuristics for determining allowable solutions can be accessed in the individual sub-problems, thereby possibly other sub-trees can be cut off early.

Assessment of the procedure

Branch - and-cut has proved over pure branch- and-bound or cutting-plane method as clearly beneficial. A major advantage of the method in practice compared with heuristics is that it is generic, so it can be used as a standard solution method for a whole range of optimization problems, while problem-specific heuristics need to be developed mostly. As a further advantage over the sole application of most heuristics, the branch-and -cut method provides an estimate of how well a solution found in comparison to an optimal solution is, without knowing it himself. The solution times to find an optimal solution together with the proof of optimality can however be very long. Indeed, it is in many integer linear programs so that good solutions can be found in a short time, the proof of optimality but takes a long time. A common, at least in the research variant is therefore to calculate the individual sub-problems with generic or problem-specific heuristics quickly good solutions whose quality can then be estimated through the entire branch-and -cut method. Upon reaching a solution, for example, is more than 5 % worse than an optimal solution, the process can be terminated when the solution quality is sufficient for practical purposes.