8 Although the Hungarian method is an efficient method for solving an assignment problem, the branch-and-bound method can also be used to solve an assignment problem.

Suppose a company has five factories and five warehouses.

Each factory’s requirements must be met by a single warehouse, and each warehouse can be assigned to only one factory. The costs of assigning a warehouse to meet a factory’s demand (in thousands) are shown in Table 77.

Let xij 1 if warehouse i is assigned to factory j and 0 otherwise. Begin by branching on the warehouse assigned to factory 1. This creates the following five branches: x11 1, x21 1, x31 1, x41 1, and x51 1. How can we obtain a lower bound on the total cost associated with a branch?

Examine the branch x21 1. If x21 1, no further assignments can come from row 2 or column 1 of the cost matrix. In determining the factory to which each of the unassigned warehouses (1, 3, 4, and 5) is assigned, we cannot do better than assign each to the smallest cost in the warehouse’s row (excluding the factory 1 column). Thus, the minimum-cost assignment having x21 1 must have a total cost of at least 10 10 9 5 5 39.

Similarly, in determining the warehouse to which each of the unassigned factories (2, 3, 4, and 5) is assigned, we cannot do better than to assign each to the smallest cost in the factory’s column (excluding the warehouse 2 row). Thus, the minimum-cost assignment having x21 1 must have a total cost of at least 10 9 5 5 7 36. Thus, the total cost of any assignment having x21 1 must be at least max(36, 39) 39. So, if branching ever leads to a candidate solution having a total cost of 39 or less, the x21 1 branch may be eliminated from consideration. Use this idea to solve the problem by branch-and-bound.

Transcribed Image Text:

TABLE 77 Factory ($) Warehouse 1 2 3 4 5 1 5 2345 10 589 17 9 52799 15 12 18 10 10 25805 25951 10 19 11 12 11 7