Procedure: Branch and bound algorithm

Description and Background

Branch and Bound algorithm is a commonly used technique in several mathematical programming applications especially in combinatorial problem when a problem is difficult to be solved directly. It is preferred over many other algorithms because it reduces the amount of search needed to find the optimal solution.

Branch and Bound creates a set of subproblems by dividing the space of current problem into unexplored subspaces represented as nodes in a dynamically generated search tree, which initially contains the root (the original problem). Performing one iteration of this procedure is based on three main components: selection of the node to process, bound calculation, and branching, where branching is the partitioning process at each node of the tree and bounding means finding lower and upper bounds to construct a proof of optimality without exhaustive research. The algorithm can be terminated whenever the difference between the upper bound and the lower bound is smaller than the chosen \(\epsilon\) or if the set of live nodes is empty, i.e. there is no unexplored parts of the solution space left, and the optimal solution is then the one recorded as “current best”.

The branch and bound procedure explained here is for finding a maximum entropy design. The computations are based on the process covariance matrix of a large candidate set of order \(N \times N\), stored as a function. Following the Maximum Entropy Sampling principle, the goal is to find the design of sample size \(\strut{n}\) whose \(n \times n\) process covariance matrix has maximum determinant. Since the design is a subset of the candidate set the design covariance matrix will be a submatrix of the candidate set covariance matrix.

Inputs

  1. Candidate set of \(N\) points
  2. A known covariance matrix (stored as a function) of the candidate points
  3. \(E\) the set of all eligible points
  4. \(F\) the set of all points forced to be in the design
  5. \(\epsilon > 0\) small chosen number
  6. A counter \(k = 0\)
  7. An initial design of size \(S_0\) of size \(n\)
  8. An optimality criterion \(I = \log \det C[S]\) (the version described is for entropy).
  9. General upper and lower bounds: \(U = Ub(C, F, E, s)\), \(L = Lb{(C, F, E, s)}\).

Outputs

  1. Global optimal design for the problem
  2. Value of the objective
  3. Various counts such as number of branchings made

Procedure

  1. Let \(k\) stand for the iteration number, \(U_k\) stand for the upper bound at \(k\) th iteration, \(I\), the incumbent, i.e. for best current value of the target function and \(L\) be the set of all unexplored subspaces
  2. Remove the problem, tuple, with max \(Ub\) from \(L\) in order to be explored.
  3. Branch the problem according to these conditions
  4. Set \(k =k+1\)
    • If \(|F|+|E|-1>s\), compute \(Ub(C, F, E\setminus i, s)\) and if \(Ub(C, F, E\setminus i, s)>U_k\), where \(i\) is any index selected to be removed from \(E\), then add \((C, F, E\setminus i, s)\) to \(L\), else if \(|F|+|E|-1=s\), then set \(S=F \bigcup E \setminus i\) and compute \(\log \det Cov[S]\), and if \(\log \det Cov[S] > I\) then set \(I=\log \det Cov[S]\) and the current design is \(S\).
    • If \(|F|+1 < s\), compute \(Ub(C,F \bigcup i, E\setminus i, s)\) and if \(Ub(C, F \bigcup i,E\setminus i, s) > U_k\), then add \((C, F,E\setminus i, s)\) to \(L\) else if \(|F|+1 < s\), then set \(S = F \bigcup i\) and compute \(\log \det S\) and if \(\log \det Cov[S] > I\) then set \(I = \log \det S\) and the current design is \(S\).
  5. Update \(U_{k+1}\) to be the highest upper bound in \(L\).
  6. Repeat steps 3,4,5 while \(U_k - I > \epsilon\).