A simulated annealing code for general integer linear programs

David Abramson*, Marcus Randall

*Corresponding author for this work

Research output: Contribution to journalArticleResearchpeer-review

19 Citations (Scopus)
4 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

Cite this