Branch and Bound

Exercises

1)  In my lecture we calculated lower bounds for the nodes in the search tree by assuming that each unassigned task would be executed by the unassigned agent who could do it at least cost.  This is like crossing out the rows and columns of the cost matrix corresponding to agents and tasks already assigned, and then adding the minimum elements from each remaining column.  An alternative method of calculating bounds is to assume that each unassigned agent will perform the task he can do at least cost.  This is like crossing out the rows and columns of the cost matrix corresponding to agents and tasks already assigned, and then adding the minimum elements from each remaining row.  Show how a branch-and-bound algorithm for the example in the lecture proceeds using this second method of calculating lower bounds.

2) Use branch-and-bound to solve the assignment problem with the following cost matrix:
 
agent/task
1
2
3
4
a
94
1
54
68
b
74
10
88
82
c
62
88
8
76
d
11
74
81
21

3)  Four types of objects are available, whose weights are respectively 7, 4, 3, and 2 units, and whose values are 9, 5, 3 and 1.  We can carry a maximum of 10 units of weight.  Objects may not be broken into smaller pieces.  Determine the most valuable load that can be carried, using branch-and-bound.