# Branch-and-bound

## 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
*H*(σ_{1},...,σ_{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

.

#### 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 2^{n}
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 *E*^{ub} 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 *E*^{ub},
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

.

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.