|
|
Introduction
The multiobjective QAP is a new combinatorial optimization problem based on the
classic QAP. This problem has been introduced by Knowles and Corne as a benchmark problem
for multiobjective metaheuristics (MOMHs), such as multiobjective evolutionary algorithms (MOEAs),
multiobjective simulated annealing, tabu search, etc.
Two problem instance generators and a small test suite are provided below. The mQAP is an unconstrained
permutation problem, suitable for benchmarking all MOEAs or MOMHs. You are encouraged to download
the publications for more information. |
Background
Many diverse planning tasks of practical importance can be formulated as instances
of the quadratic assignment problem (QAP), an NP hard
combinatorial optimization problem that dates back to the early sixties.
Applications have included back-board
wiring of electronic circuits (Steinberg 1961), facility location
problems including hospital planning (Elshafei 1977), and certain
kinds of scheduling (Geoffrion 1976).
The QAP is an unusually
difficult problem, where even relatively small (n > 20) general instances
cannot be solved to optimality, and it has thus been important in
stimulating research in approximate methods.
|
|
The multiobjective QAP (mQAP), with multiple flow matrices (defined below)
naturally models any facility
layout problem where we are concerned with the flow of more than one
type of item or agent. For example, in a hospital layout problem we may
be concerned with simultaneously minimizing the flow/distance
products of doctors on their rounds, of patients,
of hospital visitors, and of pharmaceuticals and other equipment.
For more detailed information see our publications.
TOP
|
|
|
- - a `C' program for generating uniform instances
- - a `C' program for generating `real-like' instances
- - some `C' code that reads in an instance file and places it in an array
|
|
The above is free software provided for academic or educational use. If used for
commercial purposes, please contact me.
TOP
|
|
|
|
The instances provided below use only a very small range of
the parameter settings available on the instance generators. You are encouraged to download the
generators and investigate more instances/classes. Note that it
is good practice to use separate instances for parameter tuning and testing of metaheuristics.
The generators allow you to do this easily.
|
|
|
|
|
TOP
|
|
|
|
For the ten-facility MQAP instances given above, Gary Lamont has
provided the following files of Pareto optima.
|
|
|
|
Notice: Gary Lamont has kindly pointed out an error in my original enumeration
of Pareto optima in the 10-facility instances. Results of this enumeration appeared in the EMO
paper listed below and are wrong in the Springer published version. However, the PDF version given below
has now been corrected, and the correct Pareto optima files are given above. Fortunately,
the original numbers of Pareto optima found, differ only slightly from the true values and no trends or other
general observations are affected by these changes.
- Knowles, J. D. and Corne, D. W. (2002) Instance Generators and Test Suites for the Multiobjective
Quadratic Assignment Problem. Evolutionary Multi-Criterion Optimization (EMO 2003) Second
International Conference, Faro, Portugal, April 2003, Proceedings, pp 295-310.
BibTeX Abstract PDF - corrected version - (Copyright Springer)
- Knowles, J.D. and Corne, D.W. (2002) Towards landscape analyses to inform the design of a hybrid local search for
the multiobjective quadratic assignment problem. In A. Abraham, J. Ruiz-del-Solar,
M. Koppen (eds.), Soft Computing Systems: Design, Management and
Applications, IOS Press, Amsterdam, pp. 271--279, ISBN 1-58603-297-6.
BibTeX Abstract PDF
TOP
|