Branch and Bound – The Dummies’ Guide

Branch and Bound: Introduction

The branch and bound technique is used to solve optimization problems, whereas the backtracking method is used to solve decision problems.

• Branch and bound build the state space tree, and find the optimal solution quickly by pruning a few of the branches of the tree that do not satisfy the bound.
• Branch and bound build the state space tree, one can find the optimal solution quickly by pruning a few of the tree branches that do not satisfy the bound.
• Branch and bound can be useful where some other optimization techniques like greedy or dynamic programming fail. Such algorithms are typically slower than their counterparts. In the worst case, it may run in exponential time, but careful selection of bounds and branches makes an algorithm run reasonably faster.
• Most of the terminologies of backtracking are used in this chapter too. In branch and bound, all the children of E nodes are generated before any other live node becomes an E node.
• The branch and bound technique, in which E-node puts its children in the queue, is called the FIFO branch and bound approach.
• And if E-node puts its children in the stack, then it is called the LIFO branch and bound approach.
• Bounding functions are heuristic functions. A heuristic function computes the node that maximizes the probability of a better search or minimizes the probability of the worst search. According to the maximization or minimization problem, the highest or lowest heuristic-valued node is selected for further expansion from a set of nodes.
• Example: FIFO Branch and Boundary Approach
• Let us try to understand the FIFO branch and bound with the help of the 4-queen problem. A state space tree generated by the FIFO branch and bound method is shown in Fig. (a).
• The solution vector for the 4-queen problem is defined by the 4-tuple X = (x1, x2, x3, x4), each xi indicates the column number of the ith queen in the ith row.
• Initially, when the chess board is empty, only node 1 would be a live node. It becomes the E node and generates the nodes 2, 18, 34, and 50, and they are kept on the live node list. These four nodes at level one represent that queen 1 is placed in columns 1, 2, 3 and 4 respectively.
• The number inside the circle indicates the order in which the nodes become E nodes. The number beside the circle indicates the order in which the nodes are generated.
• When all the children of node 1 are generated, node 2 is selected as the E-node. It generates nodes 3, 8, and 13. Queen Q2 cannot be placed in column 2, so node 3 is killed using the bounding function. Nodes 8 and 13 are added to the list of live nodes, and node 18 becomes the next E node. It generates nodes 19, 24, and 29. If Q1 is in the 2nd column, we cannot place Q2 in either column 1 or 3, so kill nodes 19 and 24. Node 29 is inserted into the list of live nodes.
• In the FIFO approach, nodes become E-nodes in the order they are generated.
• Node 34 will be the next E node. It generates children’s 35, 40, and 45. If Q1 is in column 3, Q2 cannot be in columns 2 and 4, so kill nodes 40 and 45. Insert node 35 into the list of live nodes. This is how this search is proceeding.
• Fig. (a) : State space tree for the 4-queen problem (method : branch and bound)

• Example: :  LC Branch and Bound Approach.
• FIFO or LIFO is very crude way of searching. It does not check the goodness of nodes. They blindly select the E node strictly in FIFO or LIFO order. In Fig. (a), node 31 is the answer node. When node 30 is generated, it should become the E-node, so that in the very next step, we get the solution. But the FIFO strategy forces the search to expand to all the live nodes generated.
  before 30.
• This search can be speeded up by using the ranking function (.) for live nodes. Consider Fig. (a). If the ranking function assigns a better value to node 30 than the remaining live nodes, then node 30 will become the E-node as soon as it is generated, and we will get the solution at the very next step, i.e., node 31.

• Example : 4 Queen Problem.
• State space tree for 4-queen problem using branch and bound and backtracking are shown in Figs. (a) and (b), respectively.
• The backtracking method explores the node in depth-first order.
• It keeps visiting nodes until it fails. Then the method backtracks.
• Nodes are explored in LIFO order. Refer to Fig. (a), at level 0, the algorithm generates node 1, then instead of generating all the children of node 1, the backtracking approach expands node 2.
• After node 2, node 6 becomes the E-node. Node 6 fails to find the solution, so the algorithm backtracks and generates another child of node 2, i.e. 8.
• Then 8 becomes an E-node and generates node 9. Thus, backtracking performs a depth-first search.
• Branch and bound cut down the node from further exploration by applying a certain bounding function to each node.
• If the node does not satisfy the bounding function, then it rejects that node.
• Node selection in the 4 queen problem using the branch and bound technique is discussed in the previous section.

Applications of Backtracking

Branch and bound technique is useful to solve problems like :

• Knapsack problem
• Travelling salesman problem
• Assignment problem
• Job scheduling problem