×

A thermodynamically motivated simulation procedure for combinatorial optimization problems. (English) Zbl 0541.90070

Summary: Exchange algorithms are an important class of heuristics for hard combinatorial optimization problems as, e.g., salesman problems or quadratic assignment problems. In Kirkpatrick’s and Cerny’s exchange algorithms for the travelling salesman problem and placement problem they propose to perform an exchange not only if the objective function value decreases by this exchange, but also in certain cases if the objective function value increases. An exchange increasing the objective function value is performed stochastically depending on the size of the increment.
Computational tests with quadratic assignment problems revealed an excellent behaviour in such an approach. Suboptimal solutions differing 1-2% from the best known solutions are obtained by a simple program in short time. By starting this program several times with different starting values all known minimal objective function values were reached. Thus this approach is well suited also for smaller computers and leads in short time to acceptable solutions.

MSC:

90C08 Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.)
90C10 Integer programming
65K05 Numerical mathematical programming methods
68Q25 Analysis of algorithms and problem complexity
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Burkard, R.E., Quadratic assignment problems, European J. operational res., 15, 3, 283-289, (1984) · Zbl 0526.90064
[2] Burkard, R.E.; Bönniger, T., A heuristic for quadratic Boolean programs with applications to quadratic assignment problems, European J. operational res., 13, 4, 374-386, (1983) · Zbl 0509.90058
[3] Burkard, R.E.; Derigs, U., Assignment and matching problems: solution methods with FORTRAN-programs, () · Zbl 0436.90069
[4] Černy, V., A thermodynamical approach to the travelling salesman problem: an efficient simulation algorithm, (1982), Institute of Physics and Biophysics, Comenius University Bratislava, CSSR, Report · Zbl 0534.90091
[5] Kirkpatrick, S.; Gelatt, C.D.; Vecchi, M.P., Optimization by simulated annealing, Science, 220, 671-680, (1983) · Zbl 1225.90162
[6] Krarup, J., Quadratic assignment, Data, 3, 72, 12-15, (1972), and unpublished data from hospital planning
[7] Metropolis, N.; Rosenbluth, A.; Rosenbluth, M.; Teller, A.; Teller, E., Equation of state calculations by fast computing machines, J. chem. phys., 21, 1087-1092, (1953)
[8] Nugent, C.E.; Vollmann, T.E.; Ruml, J., An experimental comparison of techniques for the assignment of facilities to locations, J. operations res., 16, 150-173, (1968)
[9] Podinovskii, V.V., Lexicographical problems of linear programming, USSR computat. math. and math. physics, 12, 249-253, (1972) · Zbl 0269.90032
[10] Steinberg, L., The backboard wiring problem: a placement algorithm, SIAM rev., 3, 37-50, (1961) · Zbl 0097.14703
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.