Article ID: | iaor2000448 |
Country: | Netherlands |
Volume: | 86 |
Issue: | 1 |
Start Page Number: | 3 |
End Page Number: | 21 |
Publication Date: | Mar 1999 |
Journal: | Annals of Operations Research |
Authors: | Abramson David, Randall Marcus |
Keywords: | programming: integer, combinatorial optimization |
This paper explores the use of simulated annealing (SA) for solving arbitrary combinatorial optimisation problems. It reviews an existing code called GPSIMAN for solving 0–1 problems, and evaluates it against a commercial branch-and-bound code, OSL. The problems tested include travelling salesman, graph colouring, bin packing, quadratic assignment and generalised assignment. The paper then describes a technique for representing these problems using arbitary integer variables, and shows how a general simulated annealing algorithm can also be applied. This new code, INTSA, outperforms GPSIMAN and OSL on almost all of the problems tested.