Least Cost Branch and Bound

Least Cost Branch and Bound is the way of finding a solution from the state space tree.

• FIFO or LIFO is a very crude way of searching. It does not check the goodness of the node. They blindly select the E node strictly in FIFO or LIFO order, without giving any preference to the node having better chances of getting answers quickly.

• 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 all the live nodes generated before 30, i.e., nodes 35, 40, 45, 51, 56, 61, 9, 11, 14, 16}.
• 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.
• Ranking basically depends on the additional effort (cost) required to reach the answer node from the live node.
• For any node x, the cost is determined by (1) the number of nodes in the subtree x that need to be generated before the answer node is generated, or (2) the number of levels from x to the answer node.
• Using the second measure, it can be seen from the
  Fig. (a) shows that the cost of an answer node is 4 (node 31 is four levels away from the root node).
• Node 39 (child of 38) is also an answer node. So the cost of nodes {18, 34}, {29, 35}, and {30, 38 is respectively 3, 2, and 1. And the remaining nodes on levels 2, 3, and 4 have a cost greater than 3, 2, and 1, respectively.
• With this approach, only 1, 18, 29, and 30 become the E-nodes. And the other nodes which are generated but not converted to E nodes would be 2, 34, 50, 19, 24, 32, and 31.
• Cost measure 1 generates a minimum number of nodes.
• If cost measure 2 is used, then only nodes that become E nodes would be on the path from the answer node to the root node.
• For any measure, searching the state space tree incurs major search time. And hence, nodes are ranked using estimated cost \[ hat{g}(.) \]
• Let \[ hat{g}(x) \] be the additional effort needed to reach an answer node from x. function \[ hat{c}(.) \] assigns ranking to node x such that,

                                    \[ hat{c}(x) \]   =   f(h(x)) + \[ hat{g} \](x)

• h(x) is the cost of reaching from x to root.
• In LC search, the cost function c(.) is defined as follows :
  • If x is the answer node, then c(x) is the cost of reaching x from the root
  • If x is not the answer node and the subtree of x does not contain the answer node then c(x) = ∞
  • Otherwise, c(x) is the cost of the minimum cost answer node in subtree x.

Control Abstraction

Least Cost Branch and Bound works as follow:

• Let T and c(.) represent the state space tree and cost function for the node in T.
• For node x ∈ T, c(x) represents the minimum cost of the answer node in the subtree rooted at x. Thus, C(T) represents the cost of the minimum-cost answer in state space T.
• Finding an exact cost function c(.) is challenging, so in practice, the heuristic function (.) is used to estimate c(.).
• Heuristic functions are often simple to compute and provide close to optimal performance.
• The algorithm for LCSearch is described below. Function Least( ) finds the live node with the minimum (.). This node is deleted from the list of live nodes and returned.
• Function Add(x) adds the new live node to the list of live nodes. Min-heap data structure is used to implement a list of live nodes so that the node with the lowest cost is always at the front. So that Least( ) function can retrieve the minimum cost node in constant time.
• The LCSearch algorithm returns the path from the answer node to the root node. To trace the path to the root, the parent index is stored with each live node x.

Algorithm for Least Cost Branch and Bound

Algorithm LCSearch(T)
// Description: Find answer node from state space tree and 
print path 
// Input : State space tree T
// Output : Success / Failure

if T is an answer node then
    output T
    return
end

E ← T		
Initialize list of live node to empty

while (true) do
    for each child x of E do
        if x is an answer node then
            output path from x to T
            return
        end
        Add(x)	
        x.parent ← E
    end

    if there are no more live nodes then
        print “No answer node”
        return
    end
    E ← Least()
end

Some Popular Problems Solved by Branch and Bound:

• Job sequencing problem using branch and bound
• Knapsack problem using branch and bound
• Travelling Salesman problem using branch and bound

---

Additional Reading: Read More