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

Burkard, R. E.; Rendl, F.

Eur. J. Oper. Res. 17, 169-174 (1984).

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

Keywords:

simulation; combinatorial optimization; heuristics; quadratic assignment; exchange algorithms; Computational tests

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, (Lecture Notes in Economics and Mathematical Systems, 184 (1980), Springer: Springer Berlin) · 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: 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) · Zbl 1431.65006
[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