Branch-and-bound

From Cophy
Jump to: navigation, search

Contents

Introduction

Branch-and-bound methods are often used for determining optimum solutions of NP-hard optimization problems. Roughly speaking, a problem being NP-hard means that we cannot expect to be able to design an algorithm whose running time is bounded by a polynomial in the size of the input. On the contrary, for these problems only algorithms are known whose running time grows exponentially in the input size, in the worst case. Branch-and-cut is a special variant of branch-and-bound in which the bounds are determined through polyhedral investigations (c.f. Polyhedral theory) and linear programming.


Of course, brute-force enumeration of all solutions is prohibitive already for small instance sizes. In order to determine optimum solutions nevertheless in practice, a clever enumerative scheme as branch-and-bound is employed. Often, for determining an optimum solution these methods need to enumerate only a small fraction of all possibilities. We explain a branch-and-bound procedure for specific physics application in the following.

Example (Branch-and-bound for Bernasconi)

Suppose we want to determine the minimum of the function H1,...,σn) in the so-called Bernasconi model. In this model n Ising spins are present on a straight line (i.e. an one-dimensional lattice with open boundary conditions) that can only attain two values, either + 1 or − 1. We need to find an assignment of these ±1 values to the variables σ1,...,σn in order to minimize its Hamiltonian (energy function) which is defined as

H(\sigma_1,\ldots,\sigma_n)=\frac{1}{n-1}
\sum_{d=1}^{n-1} \left(\sum_{j=0}^{n-d-1} \sigma_j \sigma_{j+d}
\right)^2.

Branching step

A branching and a bounding scheme are the main ingredients of the algorithm. In the branching step, one of the variables σi∈σ1,...,σn is chosen and eliminated from the problem formulation by creating two sub problems in one of which we fix σi = + 1, in the other σi = − 1. Each of the two sub problems is solved recursively. Using only branching steps without bounding to be explained next, we would end up enumerating all 2n solutions. In order to reduce this number in practice, we introduce upper and lower bounds.

Bounding step

A sub problem is solved by determining upper and lower bounds on its optimum solution value. The energy value Eub of the best known configuration serves as upper bound. The latter is updated whenever a better configuration could be determined. The determination of the lower bound, however, is trickier. Usually, there is not a unique way for determining these lower bounds.

If a sub problem's lower bound attains a higher value than Eub, no configuration with lower energy can be contained in it. Thus, it can be excluded from further consideration. This is usually called fathoming. For designing a practically effective algorithm, it is crucial to employ a strong lower bound with which sub problems can be fathomed early, keeping their total number reasonably small. For example, a lower bound on the Bernasconi model is given by

\min_{\sigma_1, \ldots , \sigma_n} H(\sigma_1, \ldots , \sigma_n) \leq \frac{1}{n-1} \sum_{d=1}^{n-1} \left(\min \sum_{j=0}^{n-d-1} \sigma_j \sigma_{j+d} \right)^2.

It is basically this bound that was used by Mertens [Mertens (1996)]. The strength of the bound can be further improved as follows. Several spin variables have been fixed to some value, all others are free. The energy contribution of the spins that are already fixed can be calculated. For the others, we look at short sequences of free spins and calculate the least amount they need to contribute to the energy.

Personal tools