A simulated annealing code for general integer linear programs

David Abramson, Marcus Randall

Research output: Contribution to journalArticleResearchpeer-review

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

Simulated annealing
Linear program
Integer
Assignment
Optimization problem
Bin packing
Traveling salesman
Graph coloring
Simulated annealing algorithm
Combinatorial optimization
Branch-and-bound

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 = "12",
day = "1",
doi = "10.1023/A:1018915104438",
language = "English",
volume = "86",
pages = "3--21",
journal = "Annals of Operations Research",
issn = "0254-5330",
publisher = "Springer",

}

A simulated annealing code for general integer linear programs. / Abramson, David; Randall, Marcus.

In: Annals of Operations Research, Vol. 86, 01.12.1999, p. 3-21.

Research output: Contribution to journalArticleResearchpeer-review

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 - http://www.scopus.com/inward/record.url?scp=0033450364&partnerID=8YFLogxK

U2 - 10.1023/A:1018915104438

DO - 10.1023/A:1018915104438

M3 - Article

VL - 86

SP - 3

EP - 21

JO - Annals of Operations Research

JF - Annals of Operations Research

SN - 0254-5330

ER -