NUS HomeQAP
Home | Up


Results on Quadratic Assignment Problem

Problem Definition

Consider the set Sn of permutations of {1,2,,n} and two nxn matrices A=(a<i-j>), B=(b<i-j>). The Quadratic Assignment Problem with coefficient matrices A and B, shortly denoted by QAP(A,B), can be stated as follows: Find a permutation p of the set Sn which minimizes the objective function Z(A,B,p), given by:

Permutation p which minimizes Z(A,B,p) over Sn is called an optimal solution to QAP(A,B), its corresponding value is called optimal value. The size n of the coefficient matrices A and B is the size of QAP(A,B). If any of the coefficient matrices A, B is symmetric, QAP(A,B) is called symmetric QAP, otherwise, QAP(A,B) is said to be asymmetric. This formulation of QAP is called Koopmans-Beckmann QAP.

Some example of QAP Instances

Benchmark QAP instances can be found in QAPLIB.

Fitness Landscape and Search Trajectory Analysis

Observable characteristics of QAP fitness landscape:

-. No "Big Valley": good solutions are scattered.

-. The distance of two good solutions can be as far as the diameter of fitness landscape (most anchor points are quite different). When drawn in FLST visualization, many points are almost touching the green border and we know that the distance from left and right border is diameter of the FL (and similarly for top and bottom border).

-. There are at least two types of QAP instances:
Type "A": Uniformly generated instances, no flow/distance dominance
Type "B": Real-life like instances, strong flow/distance dominance, many zeros

QAP Type A, anchor points are spread, landscape smooth. Most anchor points are classified into one major data class only (green triangles~>1% off best known solution)
 

QAP Type B, anchor points are spread,
landscape very rugged. The anchor points are of different qualities, very good (blue circles~<1% off) to very bad (black dots~>3% off)
 

Some observable Ro-TS behavior:

1. Ro-TS-I (vdf) on tai35a (QAPLIB)

The standard Ro-TS algorithm performs reasonably good for type A instances. This may be because the fitness landscape is smooth. So, most of the time, the search is traversing areas with solution quality roughly 1%++ off from best known solution value. The question is: can we do better?

Here, we do not see obvious solution cycling issue (the search appears in one region at one time and another region at another time). Note that since we do NOT record all the points, only when the search trajectory is near some of these APs then circles showing the search trajectory is drawn!

 


 

2. Ro-TS-A (vdf) on tai35a (QAPLIB)

To attack type "A", stronger intensification is preferred, avoid missing good solutions when the search are actually already near the good solutions. We achieve this by lowering the tabu tenure range used in Ro-TS. The result is a Ro-TS search that performs slightly better than Ro-TS-I on this particular fitness landscape type.

Note that the best found solution is always drawn in the middle of the screen, with other anchor points are laid out w.r.t distance to this best found solution and to other APs. Some layout errors are there but minimized using spring model layout algorithm.

 


 

3. Ro-TS-I (vdf) on tai35b (QAPLIB)

The standard Ro-TS algorithm performs very poor on type B instances. This may be because the fitness landscape is rugged. We observed that the search is stuck in a deep local optima most of the time. How to fix it?

 


 

4. Ro-TS-B (vdf) on tai35b (QAPLIB)

To attack type "B", strong diversification is needed, avoid wasting time escaping deep local optima. We perform strong diversification (but not random restart) every time Ro-TS encountered a certain number of iterations elapsed without improvement. The result is a Ro-TS search, a 'far' jump to another area in the fitness landscape, Ro-TS again, and another jump, and so on. Every region is only visited briefly, but the chance of visiting one of the good regions increased by a lot rather than being stuck in a local optima region only.

References

These results are reported in more details in our publications (download the local copy of those papers here):

  1. S. Halim, R. Yap, H.C. Lau. An Integrated White+Black Box Approach for Designing and Tuning Stochastic Local Search. In Principles and Practice of Constraint Programming (CP 2007, Providence, Rhode Island, USA, September 23-27, 2007): 332-347

  2. S. Halim, R. Yap. Designing and Tuning SLS through Animation and Graphics: an Extended Walk-through. In Engineering Stochastic Local Search Workshop (SLS 2007, Brussels, Belgium, September 6-8, 2007): 16-30

This document, results_qap.html, has been accessed 3449 times since 05-Sep-08 17:52:06 SGT. This is the 2nd time it has been accessed today.

A total of 1730 different hosts have accessed this document in the last 3336 days; your host, 54.80.148.252, has accessed it 1 times.

If you're interested, complete statistics for this document are also available, including breakdowns by top-level domain, host name, and date.