|
|
Combinatorics |
|
-Quadratic
Assignment Problem |
|
|
To illustrate the add-in we consider
a small problem described by Ronald Rardin in his book Optimization
in Operations Research. The example illustrates a location
problem, one of the applications of the QAP. Another example
is found in the section on Facility
Layout.
A small shopping mall has four shop locations. The walking
distance, in feet, between all pairs of locations are shown
in the table below.
Distance |
1 |
2 |
3 |
4 |
1 |
0 |
80 |
150 |
170 |
2 |
80 |
0 |
130 |
100 |
3 |
150 |
130 |
0 |
120 |
4 |
170 |
100 |
120 |
0 |
Four shops, designated A, B, C and D, are to be assigned to
the four locations in such a way that customers traveling between
pairs of shops will not walk too far. We have data on the number
of customers per week that travel between the shops. The data
is shown in the table below. The entries are in thousands of
trips. We show the trips in the upper diagonal of the table
although the trips might be in either direction. Although the
program can handle directional travel, the distribution of trips
between the two directions doesn't matter for a symmetric distance
matrix.
Trips |
A |
B |
C |
D |
A |
0 |
5 |
2 |
7 |
B |
0 |
0 |
3 |
8 |
C |
0 |
0 |
0 |
3 |
D |
0 |
0 |
0 |
0 |
The problem is to specify a location for each department. Call
x(i) the location assigned to department i
and say that there n departments (and locations). The
distance between two locations, say k and l,
is d(k, l) and the flow between two
department, say i and j, is f(i,
j). The trip-distance contributed by departments i
and j to the objective function is:
f(i, j)*d(x(i),
x(j))
Summing over all department pairs provides the
QAP objective function:
Sum(i = 1…n)[Sum(j
= 1 to n, i <> j){f(i,
j)*d(x(i), x(j))]
We will see that this objective is efficiently
represented using Excel functions. |
Creating a Model
|
To create a model, we choose the
QAP command from the menu. The dialog accepting the
parameters of the model is presented.
For the example, we enter 4 as the number of departments
and specify a name for the problem. As usual, this name should
be short and it must not include spaces or punctuation. The
name provides the worksheet name and is the prefix for a number
of array names on the worksheet, so once specified, it cannot
be changed. We choose to minimize the objective. The check boxes
at the bottom of the dialog determine whether assignment costs
are to be provided and whether random data are to be placed
in the problem arrays.
The add-in creates a worksheet with the name Lay
and calls the Optimize add-in to create a permutation
combinatorial form. We have entered the interlocation distances
and the interdepartmental flows into the matrices constructed
by the add-in. The initial solution assigns the locations to
the departments in numerical order and places the solution in
row 9. |
|
We see a third matrix, the Sorted
Distance matrix, at the bottom of the form that plays an
important role in the model. For the solution {1, 2, 3, 4},
the matrix is the same as the Distance matrix, however,
for other solutions the rows and columns of the distance matrix
are sorted according to the permutation solution. Each cell
of the Sorted Distance matrix holds an Excel
Index function. For example the formula in cell D26
is:
=INDEX(Lay_Distance,C26,D25)
This function returns the entry in the Distance matrix
that is in the row and column given in cells C26 and D25 respectively.
In this case it is the entry Distance(1,1), which happens to
be zero.
The INDEX functions provided by Excel perform the primary evaluation
step for a solution. Since Excel performs built-in functions
very rapidly, this approach is much more efficient than referring
to a user-defined function. On the other hand, the number of
function calls required is the square of the number of departments.
This may result in difficulties for large problems.
Row 11 for the example is colored pink and has the title Obj.
Terms. This array is not used for the example, but can
hold formulas or values that are in included in the objective
function. The function in cell F5 used to evaluate the solution
is
=SUMPRODUCT(Lay_Flow,Lay_SortDist)+ SUM( Lay_OpObjTerms)
The first term computes the QAP objective and
the latter term sums the contents of row 11.
The button in cell A3 initiates a search process.
On pressing this button, the Search dialog from the Optimize
add-in is presented. Any of the search procedures can be
selected, although the Greedy algorithm will not work
for the QAP. Since the example is so small, we have chosen the
Exhaustive enumeration option. The example has 24 permutations,
so we have set the dialog to show all of them. The search option
can also be reached by the Search command from the
Optimize menu. |
|
The results of the enumeration are shown below. The optimum
solution places shop A in location 1, shop B in location 4,
shop C in location 3 and shop D in location 2. The trip-feet
traveled is 3260 (thousands) per week. The Sorted Distance
matrix reflects the permutation in row 9.
|
|
The 24 solutions are placed in
the list shown at the left. The optimum is repeated so the total
number evaluated is 25. Since there are only 24 permutations
of 4 numbers, the list shows all solutions.
|
Assignment Costs
|
Say the shop owners offer
different rent payments for the locations and some locations
are not suitable for certain shops. These features are
added by clicking Include Assignment Cost box.
|
|
Another matrix is included
on the form called C(i,j). This gives the cost for making
specific assignments. Here we enter the rent offers as
negative numbers. Since the QAP objective is trip-feet
per week, we are subtracting from that term the revenue
per week from rents. It is not really correct to combine
terms with different dimensions. Essentially we are equating
the cost of 1000 trip-feet to 1$ in rent.
The cells with *** indicate assignments that are not
allowed. Although the initial solution uses disallowed
assignments, the search processes will not allow them. |
The solution process enumerates all possible permutations
that do not use the disallowed assignments and returns the optimum.
|
Eliminating the restricted
assignments, the location problem now has only 11 feasible
solutions. The solutions sorted by objective function
value are shown at the left. |
Larger Problems
|
A second example involves six departments and randomly
generated data. The solution of the model found with exhaustive
enumeration is shown in row 9.
|
|
Exhaustive enumeration requires 5040 function evaluations.
The top 20 solutions are listed below. Since the evaluations
use Excel functions, the time required is a modest 19
seconds on the author's computer.
|
|
We add the assignment cost
feature to the problem above and indicate that 50% of
the assignments are to be disallowed. Since a random generation
procedure is used, the fraction of disallowed cells will
be only approximately 50%.
|
|
The add-in estimates that 2250 solutions will be enumerated,
but there are only 189 feasible permutations. The estimation
procedure is not very accurate when some of the assignments
are disallowed. |
|
The figure below shows the sorted solutions
for a problem with 12 departments. The number of permutations
is far too large for exhaustive enumeration. Alternatively,
we have randomly generated 100 permutations and subjected
each to a 2-change improvement process. The results required
over 25,000 objective function evaluations and 164 seconds.
There is no way to tell if the best solution found is
the optimum. |
|
|
The add-in places no limitation on the size of the problem
that can be modeled except the limits imposed by the size of
the Excel worksheet and whatever limits Excel may impose on
the number of functions that may placed on a worksheet. Of course
larger problems are hard to solve. Certainly exhaustive enumeration
is impossible for problems with more than 10 departments unless
the allowed assignments are highly restricted. The greedy enumeration
method of the Optimize add-in does not work for this problem,
but random generation is certainly possible. The n-change improvement
option can be applied to the randomly generated solutions, and
given sufficient time, one should be be able to find good solutions
to practical problems.
|
|
|
|
|