Table 9.7 Subtract from Each Column the Diagonal Entry in that Column: = 30 + 40 + 60 + 50 + 70 + 100 = 350.

Table 9.8 Subtract from Each Row the Minimum Entry of that Row: = 350 + 0 + (-10) + (-10) + (-30) + (-30) -t-(-30) = 240.

row entries is continued, as shown in Tables 9.9, 9.10, and 9.11, at which point R = 350.

The beginning node of the branch-and-bound tree corresponds to being able to make any assignment, feasible or not. The minimum total cost has a lower bound of 350. This corresponds to the cost of the diagonal assignment. Let an entry in the row and /" column of the cost matrix be denoted by c,j. In general, branching to the right from a node will imply the assignment of a particular pair of facilities to a particular pair

Table 9.9 Subtract Diagonal Entries from Each Column: R + 0 + 10 -H 10 + 30 + 30 + 30 = 350.

Table 9.10 Subtract Minimum Entry from Each Row: = 350 + 0 + 0 4- 0 -t- (-10) + (10) + (-10) = 320.

of locations. We will use the notation: A -D *- 1 - 3, for example, to denote the assignment of facilities 1 and 3 to the locations A and D. A branch to the left means the particular assignment is to be prohibited. We will denote this by: A-D 1 - 3, for example. Each succeeding node to be chosen is decided by the following rule:

Selection of Next Node-Choose an entry c in cost matrix for the next node so that:

= max { ,} where e,i = smallest entry in row i, omitting c,j + smallest entry in column , j, omitting c,j.

Table 9.12 indicates the flf values in the upper right of each cell; max [e,j] = 10 = Branching to the left is denoted on the tree by A-D, branching to the right by A-D. The new lower bound of the left branch node is equal to the lower bound of the previous node plus dj. The new lower bound of the right branch node is equal to the lower bound of the previous node plus the reducing constants obtained after cost matrix is restricted.

Restriction consists of an examination of remaining entries in cost matrix to see if they correspond to acceptable assignments. If an entry

is not acceptable, the entry is deleted to remove it from further consideration. Consider a hypothetical example with five facilities as shown in Table 9.13. Suppose facility pair 3-4 has been assigned to location pair B -E (facility 3 is at location or E, with facility 4 at the other location). The entries in the B -E row and the 3 - 4 column have been deleted except the intersection Cg,o, which is equated to zero. Then the location pairs not assigned are A -C, A -D, and C-D. In the rows with these labels, keep those entries whose column labels are facility pairs not assigned (in this case 1-2, 1-5, and 2 - 5); but delete entries from columns labeled 1 - 3, 1 -4, 2 - 3, 2-4, 3 - 5, and 4-5, as they have a 3 or a 4 in their labels. In the remaining rows (labeled A-B, A-E, B -C, B-D, B-E, C-E, D-E), keep entries from columns 1-3, 1-4, 2-3, 2-4, 3 - 5, and 4 - 5, but delete entries with columns labeled 1-2, 1-5, and 2-5. Any reduction can now be made, ignoring deleted entries.

Using these rules, the branch-and-bound method is applied to the example in Tables 9.14 to 9.24.

Table 9.13 Xs Indicate Entry Retained in the Matrix (Partial Assignment, B-E 3-4).

Table 9.14 Restriction as Result of 6,, Assigning 2-4 to A-D: Reduction Now Possible on Row 5.

Location Pair

Facility Pair

A-D A-C B-D A-B B-C C-D

Table 9.15 Reducing Constant 10 Added to 350 for Lower Bound on Right Branch [branching will continue from left node (A-D

Location Pair

A-D A-C B-D

.350

Ail Possible (Assignmentsl

Table 9.16 Branch on Node A-D 2-4 (c,, is set equal to oo to block assignment of 2-4 to A-D; row 1 reduced by 10; 0„ - 10 selects node A-D - 1-3).

Facility Pair

Table 9.17 Restriction as a Result of e, Assigning 1-3 to A-D (the entries in A-D row and 1 -3 column deleted; zero entered in reduction now possible on row 5).

Table 9.18 Reducing Constant 20 Added to 360 to Become the Lower Bound for Node A-D 1-3 (branching continues at node A-D 2-4, which now has the least lower bound of any of the active nodes).

Table 9.19 Branching on Node A-D 2-4 Where = 20 = max {e,j\ (bound for node A-C 2-3 thus becomes 360 + 20 = 380; Table 9.19 derives directly from Table 9.14).

At this point the branch to the right from node A-D 2 - 4 to node A-C <- 2 - 3 specifies the complete assignment

. This

2 13 4

assignment has a total cost of 430. The next branch is thus from node A-D <- 1 - 3, which has a lower bound of 370. The complete branch-and-bound tree appears in Figure 9.4 with the two optimal solutions.

Possible lAssignmentsl