The Quadratic Assignment Problem

MALLBA  (TIC1999-0754-C03)



The quadratic assignment problem is defined as follows:

Given n items and flows aij (i,j=1,..., n) from item i to item j, n locations and distances bkl  between locations k and l  (k,l=1,..., n).    We want to assign one location to each item so as to minimize the sum of products of flows and distances.
 

More formally, we search for a permutation  of n items such that minimizes (the objective function)

where  is the location assigned to item i.


  Implementation of QAP with the TS skeleton

 
We have used the TS skeleton to implement the Quadratic Assignment Problem.  The design part of an instanced problem is equal to the design part of the skeleton, just because this part describes the internal working of the method and that part is generic enough not to depend on the problem.  The part to be filled by the filler user depends totally on the problem to be instanciated.

All files (skeleton filler's part and skeleton designer's part) are available in the compressed file newQAP.tar.gz.

To instanciate a problem with the Tabu Search skeleton a structure for maintaining and managing the tabu movements must be supplied.  A list structure is given by default with the skeleton code (file TabuList.cc), but the user can implementate a more efficient and particular one (taking benefit from the concrete problem that he/she instanciates).  That is what has happened with the QAP.  The file UserStructureQAP.cc provides an alternative implementation for the TabuStorage class based on a matrix.

To include the default implementation (based on lists) the filler user only has to link his/her instanciated classes with the file TabuList.cc .  Something like this would appear in the Makefile:

        QAP.list.seq:   QAP.imp.o  QAP.o  TabuList.o Main.o
        $(CXX) $(LDFLAGS) $^ -lL -lmallba -lpvm3 -o $@

To use an alternative implementation of the TabuStorage class,  a .cc file has to be filled with a source code for all its methods, and then link this .cc file with the rest of the classes.  Something like this would appear in the Makefile:

        QAP.seq:   QAP.imp.o  QAP.o  UserStructureQAP.o Main.o
$(CXX) $(LDFLAGS) $^ -lL -lmallba -lpvm3 -o $@


  Inputs needed

Two inputs are needed for the execution of a QAP instance:


These input values can be stored in an ascii file and introduced to the program using the << operator.   The state of the algorithm is reported to the standard output every iteration.   Some statistics are also reported at the end of every run.

But it's also possible to see the evolution of the algorithm while executing it because we have introduced an "observer" that draws the behavior of the fitness along the iterations and shows the main data related to the results obtained so far.   See how the observer looks like.
 

  Brief comparison with other benchmarks

 
Benchmark N Best fitness known for the benchmark Best fitness obtained by us
1st round

(10 trials, 100 it/trial & Tabu size=N)

2nd round

(50 trials, 5000 it/trial  &  Tabu size=N)

time in seconds
(10 trials, 1000 it/trial  &  Tabu size=N )
fitness
fitness
gap %
tai9.dat
9
94622
94622
94622
0
6.87
tai10.dat
10
135028
135028
135028
0
9.15
tai12.dat
12
224416
224416
224416
0
18.49
tai15.dat
15
388214
388250
388214
0
43.27
tai20.dat
20
703482
721976
 705622
0.30 
108.82
tai50.dat
50
4941410
5105140
 5052310
2.24 
3339.36
tai64.dat
64
1855928
1857650
tai80.dat
80
13557864
13856100
scr12.dat
12
31410
31410
31410
0
18.58
scr15.dat
15
51140
51140
51140
0
40.92
scr20.dat
20
110030
110058
110030
0
118.90
sko100a.dat
100
152002
153556
sko100b.dat
100
153890
155132
sko100c.dat
100
147862
150044
sko100d.dat
100
149576
152298
sko100e.dat
100
149150
151822
sko100f.dat
100
149036
152356
rou12.dat
12
235528
235852
235528
0
19.30
rou15.dat
15
354210
354210
354210
0
36.55
rou20.dat
20
725522
730090
726100
0.07
114.09
wil50.dat
50
48816
49002
wil100.dat
100
273038
276290
kra30a.dat
30
88900
90720
90720
2.04
550.39
kra30b.dat
30
91420
91590
 91590
0.18 
539.21
ste36c.dat
36
8239110
8302920
 8302920
0.77 
1160.54
bur26d.dat
26
 3821225
3.82131 e+06
3821225
0
360.88
esc128.dat
128
64
64
ste36b.dat
36
15852
16808
 16112
1.64
1221.77
tai150b.dat
150
498896643
 5.10913 e+08
tai35a.dat
35
 2422002
2.47596 e+06 
 2458830
1.52
922.21
tai100a.dat
100
21125314
2.15597 e+07
nug30.dat
30
6124
6176
 6128
0.06
541.32
tai256c.dat
256
44759294
4.48982 e+07

 
 
  
 

                                                                                                         MALLBA
                                                                                           Last update: Wed Sep 6  2000