FIFO Branch and Bound

FIFO branch and bound always use the oldest node in the queue to extend the branch. This leads to a breadth-first search, where all nodes at depth d are visited first, before any nodes at depth d+1 are visited.

In LIFO (last in, first out), the branch is always extended from the youngest node in the queue. This results in a depth-first search, in which the branch is extended via every first child encountered at a certain depth until a leaf node is found.

In LC (lowest cost) method, according to a cost function, the branch is extended by the node with the lowest extra costs. As a result, the cost function determines how to traverse the search space.

The Branch and Bound method employs either BFS or DFS search. During BFS, expanded nodes are kept in a queue, whereas in DFS, nodes are kept on the stack. BFS approach is the first in, first out (FIFO) method, while DFS is the last in, first out (LIFO). In the FIFO branch and bound, expanded nodes are inserted into the queue, and the first generated node becomes the next live node.

Assume that Fig. (a) is the collection of nodes expanded in a state-space tree during some problem-solving stage. Each cell in the queue represents the cost of the expanded node. Ni represents the order of node generation. FIFO will select N1 as the next E-node, because that node was inserted first in the queue. Similarly, LIFO approach will select node N5 as the next E-node, as it was inserted last in tht queue. LC approach does not depend on the order of insertion in the queue. Rather it selects the node based on the cost. The node with minimum cost will become the next E-Node in LC method, i.e. node N4 will be expanded next.

Control abstraction for the FIFO branch and bound technique is shown here.

Algorithm for FIFO Branch and Bound

Algorithm BB_FIFO()
// T is the state space tree and n is the node in tree T

if T is answer node then
  u ← min(cost[T], upperBound(T) + E)
  print (T)
  return
end
E ← T
while (true)
  for each child x of T do
    if x is answer node then
      print “Display path from x to root”
      return
    end
    ENQUEUE(x) // Insert new node at the end of QUEUE
    x.parent ← E	// π[x] indicates parent of x
    if x is answer node AND cost(x) < upperBound then
      u ← min(cost[T], ub(T) + E)
    end
  end
  if no more live nodes then
    print “No live node exists”
    print “Minimum cost :”, ub
    return n
  end
  E ← DEQUEUE()     // Remove front node from the QUEUE
end

Examples are discussed in the next posts. A very popular knapsack problem has been solved using both approaches.

---

Additional Reading: Read More