MALLBA (TIC1999-0754-C03)

The quadratic assignment problem is defined as follows:Given

items and flowsnfrom itema_{ij}(i,j=1,..., n)to itemi,jlocations and distancesnbetween locationsb_{kl }andkl. We want to assign one location to each item so as to minimize the sum of products of flows and distances.(k,l=1,..., n)

More formally, we search for a permutation of

items such that minimizes (the objective function)nwhere 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 fileUserStructureQAP.ccprovides 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 neededTwo inputs are needed for the execution of a QAP instance:

The

problem, that consists of :

- a number indicating the dimension (N) of the flows matrix and distances matrix (both NxN)
- the matrix of flows
- the matrix of distances

Thesetup parametersneeded (by now) are:

- the number of independent runs
- the number of iterations per run
- a boolean indicating if the fitness can be computed using a delta function
- the maximum number of neighbors to explore (a negative value implies full exploration)
- the size of the tabu structure (typically called tabu size)
- the minimum number of iterations that a movement is considered tabu
- the maximum number of iterations that a movement is considered tabu

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.87tai10.dat 10 135028 135028 135028 0 9.15tai12.dat 12 224416 224416 224416 0 18.49tai15.dat 15 388214 388250 388214 0 43.27tai20.dat 20 703482 721976 705622 0.30 108.82tai50.dat 50 4941410 5105140 5052310 2.24 3339.36tai64.dat 64 1855928 1857650 tai80.dat 80 13557864 13856100 scr12.dat 12 31410 31410 31410 0 18.58scr15.dat 15 51140 51140 51140 0 40.92scr20.dat 20 110030 110058 110030 0 118.90sko100a.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.30rou15.dat 15 354210 354210 354210 0 36.55rou20.dat 20 725522 730090 726100 0.07 114.09wil50.dat 50 48816 49002 wil100.dat 100 273038 276290 kra30a.dat 30 88900 90720 90720 2.04 550.39kra30b.dat 30 91420 91590 91590 0.18 539.21ste36c.dat 36 8239110 8302920 8302920 0.77 1160.54bur26d.dat 26 3821225 3.82131 e+06 3821225 0 360.88esc128.dat 128 64 64 ste36b.dat 36 15852 16808 16112 1.64 1221.77tai150b.dat 150 498896643 5.10913 e+08 tai35a.dat 35 2422002 2.47596 e+06 2458830 1.52 922.21tai100a.dat 100 21125314 2.15597 e+07 nug30.dat 30 6124 6176 6128 0.06 541.32tai256c.dat 256 44759294 4.48982 e+07

MALLBA

Last update: Wed Sep 6 2000