Branch and Bound

Exhaustive or Complete enumeration is possible only for a limited set of variables because of the exponential growth of effort required to examine all possible solutions. The Branch and Bound  (BB) algorithm is one of the successful algorithms to use selective/partial enumeration rather than complete enumeration.   They do so by using  relaxation models instead of the original complete discrete mathematical models. The Branch and Bound (BB) algorithms uses a tree structure    to represent completions of partial solutions. The tree structure uses nodes and edges/links to represent the trail of partial solutions. This is called fathoming the partial solution. The terminology is borrowed from operation research literature [3] and is explained below with respect to Example 8.1 which is reproduced below for convenience.    
 
Example 8.1
Minimize
 ex 8.1
Side Constraints ex 5.1

Definitions

Partial Solution    A solution in which some  discrete design variables are fixed and others are left free or undetermined. Variables that are not fixed are represented by the symbol ‘f’. For example

bb

represents the optimization problem with x2 = 0.5 and x1 and x3 to be determined. The partial solutions are also termed as the nodes of the tree. The free variables are usually solved using a continuous relation of the model.


Completions (of Partial Solution)    Each partial solution or node can give rise to additional partial solution/nodes directly under it. This is called branching or expansion of the node. In this new set of nodes another one of the free discrete variables is fixed and the remaining still continue to be free. For example under the node represented above, five additional nodes are possible

bb completions

These completions branch out and hence a tree like structure. There is a hierarchical structuring of the nodes. Each branch represents leads to a tier in which some variable is held at its prescribed discrete value.


Active Partial Solution:  A node that has not been terminated or pruned and has not been completed.

Fathoming the Partial Solution    Expanding the node all the way till the end is termed fathoming a node. During the fathoming operation it is possible to identify those partial solutions at a node that do not need not be investigated. Only the best solution at the node is branched. Those partial solutions/nodes that will not be investigated further are pruned or terminated in the tree.

Edges/Links     These are node to node connections in a in a tree. They identify the value of the new variable that is fixed.

Root:     The BB algorithm searches along this tree. It starts at the root where all the design variables are free. BB search stops when all partial solutions in the tree has been branched or terminated. The search is depth first – completion at a node is preferred to jumping across nodes in the same hierarchy.

Incumbent Solution    The incumbent solution is the best feasible solution known so far with all discrete variables assuming discrete values. When the BB search finally stops, the final incumbent solution, if one exists, is a global optimum solution. In the following the incumbent solution is denoted by f**. The incumbent design variables are X**.


Algorithm: Branch and Bound – A8.2

For even a small set of discrete variables actually drawing the BB tree structure is most likely a difficult enterprise. The tree structure merely identifies the search process. Example 8.1 did not have constraints so feasibility was not examined. With constraints present, choosing the partial solution to complete based on minimum value of the objective function is not a justifiable strategy. The best feasible solution is the candidate for completion. Also, an active feasible partial solution that has a better value than the current incumbent solution is also a candidate for completion. The following algorithm captures the essence of the Branch and Bound Algorithm.

Step 0
 Establish the root node with all discrete variables free.
Initialize solution index s to 0
Set current incumbent solution to f** = inf,   X** = [inf], (minimization problem)

Step 1
 If any active feasible partial solutions remain (that is better then the current incumbent solution), select one as X(s) and go to Step 2 
    If none exists and there exists an incumbent solution  it is optimal.
    If none exists and there is no incumbent solution the model s infeasible.
Step 2
 Obtain the completion of the partial solution X(s) using a continuous relaxation of the original model. 

Step 3
 If there are no feasible completions of the partial solution X(s), terminate X(s) , increment s to  s + 1 and return to Step 1.
Step 4
 If the best feasible completion of partial solution X(s) cannot improve the incumbent solution then terminate X(s),  increment s to s + 1 and return to Step 1
Step 5
 If the best feasible completion is better then the incumbent, update the incumbent solution
    f**  f(s),     X**  X(s)
terminate X(s) , increment s to s + 1 and return to Step 1.

Example 8.2  The mathematical model for Example 8.2, where x1, and x2 are integers.

Minimize ex 8.2
Subject to
 ex 8.2
Side Constraints
 ex 8.2

The solution is  ex 8.2 sol

To focus on the method and keep the figure compact, the discrete set for the design variables are reduced to 4 values around the solution:
ex 8.2 sol

Applying Branch and Bound Algorithm:    The BB tree is shown in Figure 8.5 (shown below). The data for the tree is calculated through BBEx8_2.m

fig 8.5
Node 0 This is the root node. All the variables are free. The continuos relaxation of the problem is solved. The solution is indicated on the tree. Currently this is the only available active partial solution and hence needs to be completed.
Nodes 1-4
 The partial solution at Node 0 is completed using variable x1 from the reduced discrete set identified above. This leads to 4 branches and the optimal values are indicated on the tree. The best values are indicated at the nodes. For this problem they are also feasible. There are now four active partial solutions.

Node 3
  The solution at node 3 is also a feasible solution of the original discrete optimization problem since the design variables are discrete and belong to the permissible discrete set. Node 3 is therefore fathomed. This provides the first incumbent solution.

There are three available active feasible partial solutions (Nodes 1,2, and 4) for completion. Since the solutions at the nodes are all feasible, only the best active feasible partial solution is picked up for completion – Node 4. Nodes 1 and 2 can be terminated.
Node 4
 Node 4 has a feasible solution better than the current incumbent solution. It is completed by branching to Nodes 5,6,7,8. Only Node 5 has a feasible solution. The best solution at Node 5 is not better than the current incumbent solution. Nodes 5,6,7,8 can be terminated.


There are no more active partial solutions and the tree has been fathomed. The current incumbent solution is the optimal solution.

The two search techniques so far in this section, namely Exhaustive Enumeration, and Branch and Bound provide the additional feature of discovering global optimum solutions.