A simulated annealing code for general integer linear programs

David Abramson*, Marcus Randall

*Corresponding author for this work

Research output: Contribution to journalArticleResearchpeer-review

23 Citations (Scopus)
11 Downloads (Pure)

Abstract

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 arbitrary 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.

Original languageEnglish
Pages (from-to)3-21
Number of pages19
JournalAnnals of Operations Research
Volume86
DOIs
Publication statusPublished - 1 Dec 1999
Externally publishedYes

Fingerprint

Dive into the research topics of 'A simulated annealing code for general integer linear programs'. Together they form a unique fingerprint.

Cite this