Was bedeutet Branch and Bound

Branch-and-bound methods are algorithms that solve an optimisation problem by successively restricting or branching decision variables. A so-called decision tree is built up in the process. Before each new branching in a node, it is checked whether the subtree under this node can even occur in an optimal solution. For this purpose, a simpler optimisation problem is solved (relaxation), which specifies a bound for the best possible solution in this subtree.

A branch-and-bound method therefore consists of an alternating process of branching and calculating bounds. A good branch-and-bound method is characterised by the fact that the relaxation can be solved quickly, the relaxation provides a value close to the optimal solution of the original problem and, on average, as few nodes as possible have to be generated in the decision tree.

Branch-and-bound methods are so-called ‘exact algorithms’. This means that they always provide an optimal solution if the computing time is long enough. Unfortunately, the computing time required for this usually increases exponentially with the runtime, so that in practice only a few classes of optimisation problems can be solved using these methods.

In route planning, so-called branch-and-price methods or branch-and-cut methods or combinations thereof (‘branch-and-price-and-cut’) are used in individual cases. These can solve certain types of (large) problems (e.g. travelling salesman problems) well.

Was bedeutet Branch and Bound - gts systems
Cookie Consent with Real Cookie Banner