Algorithm
-
Getting Started with AlgorithmWhat is an Algorithm?
-
Characteristics of Algorithm1 Topic
-
Analysis Framework
-
Performance Analysis3 Topics
-
Mathematical Analysis2 Topics
-
Sorting AlgorithmSorting Algorithm10 Topics
-
Searching Algorithm6 Topics
-
Fundamental of Data StructuresStacks
-
Queues
-
Graphs
-
Trees
-
Sets
-
Dictionaries
-
Divide and ConquerGeneral Method
-
Binary Search
-
Recurrence Equation for Divide and Conquer
-
Finding the Maximum and Minimum
-
Merge Sort
-
Quick Sort
-
Stassen’s Matrix Multiplication
-
Advantages and Disadvantages of Divide and Conquer
-
Decrease and ConquerInsertion Sort
-
Topological Sort
-
Greedy MethodGeneral Method
-
Coin Change Problem
-
Knapsack Problem
-
Job Sequencing with Deadlines
-
Minimum Cost Spanning Trees2 Topics
-
Single Source Shortest Paths1 Topic
-
Optimal Tree Problem1 Topic
-
Transform and Conquer Approach1 Topic
-
Dynamic ProgrammingGeneral Method with Examples
-
Multistage Graphs
-
Transitive Closure1 Topic
-
All Pairs Shortest Paths6 Topics
-
BacktrackingGeneral Method
-
N-Queens Problem
-
Sum of Subsets problem
-
Graph Coloring
-
Hamiltonian Cycles
-
Branch and Bound2 Topics
-
0/1 Knapsack problem2 Topics
-
NP-Complete and NP-Hard Problems1 Topic
Participants2253
Assignment Problem
Let us illustrate the branch-and-bound approach by applying it to the problem of assigning n people to n jobs so that the total cost of the assignment is as small as possible. Recall that an instance of the assignment problem is specified by an n × n cost matrix C so that we can state the problem as follows: select one element in each row of the matrix so that no two selected elements are in the same column and their sum is the smallest possible.
Let there be N workers and N jobs. Any worker can be assigned to perform any job, incurring some cost that may vary depending on the work-job assignment. It is required to perform all jobs by assigning exactly one worker to each job and exactly one job to each agent in such a way that the total cost of the assignment is minimized.

How can we find a lower bound on the cost of an optimal selection without
actually solving the problem? We can do this by several methods. For example, it is clear that the cost of any solution, including an optimal one, cannot be smaller than the sum of the smallest elements in each of the matrix’s rows. For the instance here, this sum is 2 + 3 + 1 + 4 = 10. It is important to stress that this is not the cost of any legitimate selection (3 and 1 came from the same column of the matrix); it is just a lower bound on the cost of any legitimate selection. We can and will apply the same thinking to partially constructed solutions. For example, for any legitimate selection that selects 9 from the first row, the lower bound will be 9 + 3 + 1 + 4 = 17.
One more comment is in order before we embark on constructing the problem’s state-space tree. It deals with the order in which the tree nodes will be generated. Rather than generating a single child of the last promising node as we did in backtracking, we will generate all the children of the most promising node among non terminated leaves in the current tree. (Nonterminated, i.e., still promising, leaves are also called live.) How can we tell which of the nodes is most promising? We can do this by comparing the lower bounds of the live nodes. It is sensible to consider a node with the best bound as most promising, although this does not, of course, preclude the possibility that an optimal solution will ultimately belong to a different branch of the state-space tree. This variation of the strategy is called the best-first branch-and-bound.
So, returning to the instance of the assignment problem given earlier, we start with the root that corresponds to no elements selected from the cost matrix. As we already discussed, the lower-bound value for the root, denoted lb, is 10. The nodes on the first level of the tree correspond to selections of an element in the first row of the matrix, i.e., a job for person a (Figure a).

problem being solved with the best-first branch-and-bound algorithm. The
number above a node shows the order in which the node was generated.
A node’s fields indicate the job number assigned to person a and the
lower bound value, lb, for this node.
So we have four live leaves—nodes 1 through 4—that may contain an optimal solution. The most promising of them is node 2 because it has the smallest lowerbound value. Following our best-first search strategy, we branch out from that node first by considering the three different ways of selecting an element from the second row and not in the second column the three different jobs that can be assigned to person b (Figure b).

problem being solved with the best-first branch-and-bound algorithm.
Of the six live leaves—nodes 1, 3, 4, 5, 6, and 7—that may contain an optimal solution, we again choose the one with the smallest lower bound, node 5. First, we consider selecting the third column’s element from c’s row (i.e., assigning person c to job 3); this leaves us with no choice but to select the element from the fourth column of d’s row (assigning person d to job 4). This yields leaf 8 (Figure c), which corresponds to the feasible solution {a → 2, b → 1, c → 3, d → 4} with the total cost of 13. Its sibling, node 9, corresponds to the feasible solution {a → 2, b → 1, c → 4, d → 3} with the total cost of 25. Since its cost is larger than the cost of the solution represented by leaf 8, node 9 is simply terminated. (Of course, if its cost were smaller than 13, we would have to replace the information about the best solution seen so far with the data provided by this node.) Now, as we inspect each of the live leaves of the last state-space tree—nodes 1, 3, 4, 6, and 7 in Figure c—we discover that their lower-bound values are not smaller than 13, the value of the best selection seen so far (leaf 8). Hence, we terminate all of them and recognize the solution represented by leaf 8 as the optimal solution to the problem.

solved with the best-first branch-and-bound algorithm.