Homework Assignment #24

Show all work neatly.

Branch and Bound for Job Assignment. In general, the Job Assignment problem involves $n$ tasks and $n$ agents. Each agent has a cost associated with its ability to complete each task. The goal is to assign each agent a unique task to minimize total cost.

Given the following Job Assignment problem with agents A-D and tasks 1-4,

     #1    #2    #3    #4
A    17    16    15    14
B    11    17    19    23
C    13    18    11    10
D    14    15    16    20

provide the necessary elements of a branch and bound algorithm for solving this problem:

Describe the required elements of a problem state (in the state space). (Think of a state as a data structure. What are its data members?)

Describe one method for computing a bound function on such states, in general.

What is the bound on the initial state (no jobs assigned to agents) using your method from question #2?

Describe one method for computing an initial BSSF for this problem.

What is the value of the initial BSSF on the problem given above using your method from question #4?

Describe a state expansion strategy; i.e., how do you generate “children” states from a parent state? Be sure that your strategy does not generate redundant states.

Also, is the B&B algorithm you have designed optimal with respect to the cost of the final solution? i.e., Does your search find the minimum cost solution? Equivalently, does your search only prune all sub-optimal states? Explain.

Now apply your algorithm to find an optimal solution. Show the execution of your search in a way that is easy for the grader to follow. What is the optimal solution that you find? How much does it cost?