Question 10.20: Illustrating the pairwise layout improvement algorithm and e...

Note that the distance matrix is asymmetric. Therefore, instead of converting the from-to flow values to flow-between values, we will leave the flow matrix F in its current form (i.e., the direction of flow is relevant). Suppose the initial solution is given by (A: 1, B: 2, C: 3, D: 4); that is, facility A is assigned to site 1, facility B is assigned to site 2, and so on. The first nonzero flow value in \mathrm{F} is a flow of 5 units from facility A to B, which is multiplied with 5 distance units (i.e., the distance from site 1 to 2 ). The next nonzero flow value in F is a flow of 2 units from facility A to C, which is multiplied by 10 distance units (i.e., the distance from site 1 to 3), and so on. The resulting total cost is given by (5 \times 5)+(2 \times 10)+(2 \times 6)+ (3 \times 7)+(3 \times 8)+(4 \times 5)+(5 \times 5)=147 units, which is also shown under the column labeled “Initial Solution” in Table 10.11 .

Pairwise machine exchange leads to six possible pairs. As shown in Table 10.11, these pairs are (AB), (AC), (AD), (BC), (BD), and (CD). We stress that once we exchange, say, machines \mathrm{A} and \mathrm{B}, and compute the new total cost, we put machines \mathrm{A} and \mathrm{B} back in their current locations before we compute the cost of exchanging machines A and C. That is, the exchanges are not cumulative exchanges; rather, each exchange is investigated one at a time relative to the current (or initial) solution. Exchanging machines \mathrm{A} and \mathrm{B}, we obtain (A:2, B:1, C:3, D:4), which yields the distance values shown in Table 10.11 under the column labeled “AB.” The resulting total cost is equal to 136 units, which is better than the initial solution, but we need to explore the remaining pairs. With the next pair, that is, (AC), we obtain (A:3, B:2, C:1, D:4), which yields a total cost of 150 units. The total cost values for the remaining four pairs are shown in Table 10.11.

Following the direction of steepest descent (i.e., the pair that yields the largest reduction in total cost), we exchange machines C and D to obtain a new solution given by (A:1, B:2, C:4, D:3) for a total cost of 132 units. Taking this solution as the current solution, we evaluate all possible pairwise exchanges again. The results are shown in Table 10.12, where the new solution we obtain is given by (A:3, B:2, C:4, D:1) with a total cost of 120 units.

Taking (A:3, B:2, C:4, D:1) as the current solution and considering all possible pairwise exchanges again, we find that no other pairwise exchange yields a total cost less than 120 units. Therefore, we stop the procedure with a two-opt solution of 120 units.

The improvement procedure described above terminates at the first “local optimal” (in this case, two-opt) solution it encounters. Furthermore, it does not allow even temporary increases in the total cost in anticipation of finding a better solution later on. As a result, the quality of the final solution depends very much on the initial solution the procedure is started with. Therefore, we recommend that the above procedure be executed with alternative initial solutions, though there is no guarantee that each initial solution will terminate at a different final solution. In those cases where the analyst feels a better solution is needed, and the incremental effort is warranted, instead of the above steepestdescent procedure, we recommend using the simulated annealing procedure described in Chapter 6 . The simulated annealing procedure described there is also based on pairwise exchanges, but temporary increases in total cost are allowed with a certain probability. We refer the reader to Chapter 6 for further details.

Whether a steepest-descent or simulated annealing-based procedure is used, we need to recognize that both procedures are heuristic procedures, and unless a very large number of runs are made, we are often left wondering how good the final solution is and how far off its total cost may be from the globally optimal solution. Of course, this is a difficult concern to address since the QAP is a difficult problem to solve and we often do not know what the total cost of the globally optimal solution might be. However, in some instances, computing a lower bound (LB) on the total cost may give us an indication on the quality of the final solution we obtain with the above heuristic procedures. Lower bounds play an important role in many combinatorial optimization problems, but an in-depth treatment of the topic is beyond our scope. Rather, using the data for Example 10.20, we will demonstrate a fairly simple lower bound developed for the QAP. The lower bound we show is reasonably “strong” for small instances of the problem. (More sophisticated bounds have been developed for larger instances of the QAP; see, for example, [1] and [30], among others.)

In reference to Tables 10.11 and 10.12, note that the total cost is computed by multiplying a set (or vector) of flow values by a set (or vector) of distance values. Of course, the appropriate distance value that each flow value is multiplied with depends on the location of the facilities, but we are still multiplying two vectors. In mathematics, it is well known that the multiplication (i.e., inner product) of two vectors is minimized if the two vectors are sorted in opposite directions. Suppose in Example 10.20 we sort all the flow values in nondecreasing order and all the distance values in nonincreasing order. Taking the inner product of the two vectors, we obtain

Hence, no matter where we assign each facility, we cannot find a solution with a total cost less than 112 units. Of course, there may be no feasible assignment of facilities to sites that produces a total cost of exactly 112 units. This should be evident from the manner in which we simply sorted the two vectors without considering the flow values associated with particular facilities and the distance values associated with particular sites. However, achievability (i.e., finding a solution with a total cost equal to 112 units) is not our main purpose in constructing a lower bound. In fact, if we could find a solution that achieves a total cost of 112 units, we would know it is the globally optimal solution. However, finding the globally optimal solution is itself a very difficult task, as we stated earlier. Hence, we generally use a lower bound not to test achievability but rather to test the quality of a heuristic solution. For the above example, we find that our two-opt solution (120 units) is approximately 7 \% above the lower bound (112 units). Since the globally optimal solution cannot be less than 112 units, we conclude that our two-opt solution is, at most, approximately 7 \% larger than the globally optimal solution. Of course, our two-opt solution may be globally optimal, but we do not know that. (We remark that lower bounds are also extensively used within branch-and-bound and other implicit enumeration procedures; such use of lower bounds is beyond our scope.)

The “stronger” a lower bound is, the more useful it becomes for optimization or evaluation purposes. For example, in Example 10.20, all the distance values and the flow values are greater than or equal to zero. Therefore, any solution must have a total cost greater than or equal to zero, which is a very “weak” lower bound because all it says is that the globally optimal solution lies somewhere between 0 and 120 units. This is not useful information compared to saying “the globally optimal solution lies somewhere between 112 and 120 units.” This point should also make it clear that there are many possible lower bounds for a given problem (i.e., a lower bound is not unique). In fact, generally speaking, the more information and problem structure we capture, the stronger the lower bound will be. However, we also have to keep the computational burden in mind; often capturing more information or structure in the lower bound means spending more time to compute the bound.

How can we strengthen the lower bound we computed in Example 10.20? As we stated earlier, there are numerous sophisticated bounding schemes developed for the QAP. We will use a fairly straightforward and easy-to-compute lower bound developed by Bazaraa and Elshafei [6]. Consider the cost of assigning facility A to site 1 . The primary difficulty with the QAP, of course, is that we cannot compute the exact cost of this assignment unless we know exactly at which sites facilities B, C, and D are located. However, we can compute a lower bound on the cost of assigning facility A to site 1 even if we do not know the location of the other facilities.

If facility \mathrm{A} is located at site 1 , the flows out of facility A (i.e., flows of 0,2, and 5 units) would have to be multiplied with distance values out of site 1 (i.e., distances of 4,5 , and 10 units). Since we do not know where the other facilities are, we do not know which distance value each flow value must be multiplied with. However, no matter which distance value each flow value is multiplied with, a lower bound on the value of this multiplication can again be obtained simply by sorting the two vectors in question in opposite directions. That is, the inner product of (0,2,5) with (10,5,4), which yields 30 units, is a lower bound. Repeating the same procedure for the flows into facility A and the distances into site 1, we obtain (0,0,3) \cdot(8,6,4)=12 units. Hence, no matter where facilities \mathrm{B}, \mathrm{C}, and \mathrm{D} are located, the cost of assigning facility A to site 1 is greater than or equal to 30+12= 42 units.

Repeating the above procedure for the remaining sites and remaining facilities, we obtain the assignment matrix shown in Table 10.13 a. Note that the resulting matrix is the well-known (linear) assignment problem, which is straightforward to solve optimally. Using the Hungarian method, we obtain the optimal solution shown in Table 10.13 b.

(The Hungarian method is shown in many operations research texts. The reader may refer to Taha [64] for a quick-and-practical exposure to the Hungarian method; for a more theoretical look at the Hungarian method, the reader may refer to Murty [52].)

Note that the solution shown in Table 10.13b is optimal for the linear assignment problem; it is not necessarily optimal for the original quadratic assignment problem because each entry in Table 10.13a is only a lower bound on the actual cost instead of the actual cost itself.

The total cost of the optimal solution to the linear assignment problem is equal to 42+67+81+40=230 units. Our heuristic solution has a total cost of 120 units. Of course, it is impossible for a lower bound to be greater than the total cost of any heuristic solution. The reason we obtained 230 units is that each “interaction” (i.e., flow \times distance) in Table 10.13 a is counted twice when we add up the assignment costs. That is, when we compute the lower bound on the cost of assigning, say, facility A to site 1, we account for the flow it has with facilities B, C, and D. However, when we later compute the lower bound on the cost of assigning, say, facility B to site 2 , we include its interaction with facility A. Hence, each (flow \times distance) value is counted twice. To compensate, we simply divide 230 by 2 to obtain a new (stronger) lower bound of L B_{2}=115 units. (Recall that L B_{1}=112 units.) Hence, we can now state that the globally optimal solution lies somewhere between 115 and 120 units, and that our heuristic solution is at most 4.3 \% above the global optimal solution.

The QAP has many applications in facilities planning (including facility location) and other areas of industrial engineering. It also has applications in electrical engineering (for example, circuit board design) and economics. As a result, the QAP has received considerable attention from researchers, and it continues to be a very active research area. The interested reader may refer to Cela [16] for a survey on the QAP.