A simulated annealing code for general integer linear programs

David Abramson; Marcus Randall

doi:10.1023/A:1018915104438

A simulated annealing code for general integer linear programs

David Abramson^*
, Marcus Randall

^*Corresponding author for this work

Research output: Contribution to journal › Article › Research › peer-review

25 Citations (Scopus)

119 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 language	English
Pages (from-to)	3-21
Number of pages	19
Journal	Annals of Operations Research
Volume	86
DOIs	https://doi.org/10.1023/A:1018915104438
Publication status	Published - 1 Dec 1999
Externally published	Yes

Access to Document

10.1023/A:1018915104438

A simulated annealing code for general integer linear programsAccepted author manuscript, 229 KBLicence: Unspecified

https://rdcu.be/cm2EgLicence: Other

Cite this

@article{2a4ee10953324c9bb98080fa81821f3c,

title = "A simulated annealing code for general integer linear programs",

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.",

author = "David Abramson and Marcus Randall",

year = "1999",

month = dec,

day = "1",

doi = "10.1023/A:1018915104438",

language = "English",

volume = "86",

pages = "3--21",

journal = "Annals of Operations Research",

issn = "0254-5330",

publisher = "Springer",

}

TY - JOUR

T1 - A simulated annealing code for general integer linear programs

AU - Abramson, David

AU - Randall, Marcus

PY - 1999/12/1

Y1 - 1999/12/1

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

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

UR - https://www.scopus.com/pages/publications/0033450364

U2 - 10.1023/A:1018915104438

DO - 10.1023/A:1018915104438

M3 - Article

AN - SCOPUS:0033450364

SN - 0254-5330

VL - 86

SP - 3

EP - 21

JO - Annals of Operations Research

JF - Annals of Operations Research

ER -

A simulated annealing code for general integer linear programs

Abstract

Access to Document

Other files and links

Fingerprint

Cite this