Solving Quadratic Assignment Problems by ‘Simulated Annealing’
The DOI matches its Crossref record; 13 of the 13 references it cites were found in a registry or an index.
Abstract
Recently, an interesting analogy between problems in combinatorial optimization and statistical mechanics has been developed and has proven useful in solving certain traditional optimization problems such as computer design, partitioning, component placement, wiring, and traveling salesman problems. The analogy has resulted in a methodology, termed “simulated annealing,” which, in the process of iterating to an optimum, uses Monte Carlo sampling to occasionally accept solutions to discrete optimization problems which increase rather than decrease the objective function value. This process is counter to the normal ‘steepest-descent’ algorithmic approach. However, it is argued in the analogy that by taking such controlled uphill steps, the optimizing algorithm need not get “stuck” on inferior solutions. This paper presents an application of the simulated annealing method to solve the quadratic assignment problem (QAP). Performance is tested on a set of “standard” problems, as well as some newly generated larger problems (n = 50 and n = 100). The results are compared to those from other traditional heuristics, e.g., CRAFT, biased sampling, and a revised Hillier procedure. It is shown that under certain conditions simulated annealing can yield higher quality (lower cost) solutions at comparable CPU times. However, the simulated annealing algorithm is sensitive to a number of parameters, some of whose effects are investigated and reported herein through the analysis of an experimental design.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Optimization by Simulated Annealing
Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983) · Science · doi:10.1126/science.220.4598.671 · Cited by 45,134
Equation of State Calculations by Fast Computing Machines
Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N., Teller, A. H., & Teller, E. (1953) · The Journal of Chemical Physics · doi:10.1063/1.1699114 · Cited by 37,192
Assignment Problems and the Location of Economic Activities
Koopmans, T. C., & Beckmann, M. (1957) · Econometrica · doi:10.2307/1907742 · Cited by 2,308
P-Complete Approximation Problems
Sahni, S., & Gonzalez, T. (1976) · Journal of the ACM · doi:10.1145/321958.321975 · Cited by 1,703
Facility Layout and Location: An Analytical Approach
Francis, R. L., McGinnis, L. F., & White, J. A. (1991) · Medical Entomology and Zoology · Cited by 1,088
The Quadratic Assignment Problem
Lawler, E. L. (1963) · Management Science · doi:10.1287/mnsc.9.4.586 · Cited by 964
A Heuristic Algorithm and Simulation Approach to Relative Location of Facilities
Armour, G. C., & Buffa, E. S. (1963) · Management Science · doi:10.1287/mnsc.9.2.294 · Cited by 740
A thermodynamically motivated simulation procedure for combinatorial optimization problems
Burkard, R. E., & Rendl, F. (1984) · European Journal of Operational Research · doi:10.1016/0377-2217(84)90231-5 · Cited by 345
The N-City Travelling Salesman Problem: Statistical Mechanics and the Metropolis Algorithm
Bonomi, E., & Lutton, J.-L. (1984) · SIAM Review · doi:10.1137/1026105 · Cited by 251
Quadratic Assignment Problem Algorithms and the Location of Indivisible Facilities
Hillier, F. S., & Connors, M. M. (1966) · Management Science · doi:10.1287/mnsc.13.1.42 · Cited by 231
A Review of the Placement and Quadratic Assignment Problems
Hanan, M., & Kurtzberg, J. M. (1972) · SIAM Review · doi:10.1137/1014035 · Cited by 169
Francis, R. L., McGinnis, L. F., & White, J. A. (1983) · European Journal of Operational Research · doi:10.1016/0377-2217(83)90194-7 · Cited by 141
Optimization by simulated annealing: A preliminary computational study for the TSP
Skiścim, C. C., & Golden, B. (1983) · NCSU Libraries Repository (North Carolina State University Libraries) · doi:10.5555/800044.801546 · Cited by 71
Cited by
A survey for the quadratic assignment problem
Loiola, E. M., de Abreu, N. M. M., Boaventura-Netto, P. O., Hahn, P., & Querido, T. (2007) · European Journal of Operational Research · doi:10.1016/j.ejor.2005.09.032 · Cited by 741
Metaheuristics: A bibliography
Osman, I. H., & Laporte, G. (1996) · Annals of Operations Research · doi:10.1007/bf02125421 · Cited by 672
QAPLIB – A Quadratic Assignment Problem Library
Burkard, R. E., Karisch, S. E., & Rendl, F. (1997) · Journal of Global Optimization · doi:10.1023/a:1008293323270 · Cited by 654
Chemical-Reaction-Inspired Metaheuristic for Optimization
Lam, A. Y. S., & Li, V. O. K. (2010) · IEEE Transactions on Evolutionary Computation · doi:10.1109/tevc.2009.2033580 · Cited by 587
An improved annealing scheme for the QAP
Connolly, D. T. (1990) · European Journal of Operational Research · doi:10.1016/0377-2217(90)90301-q · Cited by 400
Metadata
- Authors
- Wilhelm, M. R., & Ward, T. L.
- Venue
- IIE Transactions
- Publisher
- Informa UK Limited
- Published
- 1987-03
- Volume
- 19
- Issue
- 1
- Pages
- 107-119
- ISSN
- 0740-817X (ISSN-L)
- 1545-8830
- OpenAlex
- W2066883591
- Cited by
- 315
- References
- 13
- FWCI
- 2.24
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.