A general meta-heuristic based solver for combinatorial optimisation problems

Marcus Randall, David Abramson

Research output: Contribution to journalArticleResearchpeer-review

22 Citations (Scopus)

Abstract

In recent years, there have been many studies in which tailored heuristics and meta-heuristics have been applied to specific optimisation problems. These codes can be extremely efficient, but may also lack generality. In contrast, this research focuses on building a general-purpose combinatorial optimisation problem solver using a variety of meta-heuristic algorithms including Simulated Annealing and Tabu Search. The system is novel because it uses a modelling environment in which the solution is stored in dense dynamic list structures, unlike a more conventional sparse vector notation. Because of this, it incorporates a number of neighbourhood search operators that are normally only found in tailored codes and it performs well on a range of problems. The general nature of the system allows a model developer to rapidly prototype different problems. The new solver is applied across a range of traditional combinatorial optimisation problems. The results indicate that the system achieves good performance in terms of solution quality and runtime.

Original languageEnglish
Pages (from-to)185-210
Number of pages26
JournalComputational Optimization and Applications
Volume20
Issue number2
DOIs
Publication statusPublished - 1 Nov 2001

Fingerprint

Combinatorial optimization
Combinatorial Optimization Problem
Metaheuristics
Tabu search
Heuristic algorithms
Simulated annealing
Neighborhood Search
Tabu Search
Simulated Annealing
Heuristic algorithm
Range of data
Notation
Heuristics
Prototype
Optimization Problem
Operator
Modeling
Model

Cite this

@article{83e18665fca344819417f8a62a0ae0af,
title = "A general meta-heuristic based solver for combinatorial optimisation problems",
abstract = "In recent years, there have been many studies in which tailored heuristics and meta-heuristics have been applied to specific optimisation problems. These codes can be extremely efficient, but may also lack generality. In contrast, this research focuses on building a general-purpose combinatorial optimisation problem solver using a variety of meta-heuristic algorithms including Simulated Annealing and Tabu Search. The system is novel because it uses a modelling environment in which the solution is stored in dense dynamic list structures, unlike a more conventional sparse vector notation. Because of this, it incorporates a number of neighbourhood search operators that are normally only found in tailored codes and it performs well on a range of problems. The general nature of the system allows a model developer to rapidly prototype different problems. The new solver is applied across a range of traditional combinatorial optimisation problems. The results indicate that the system achieves good performance in terms of solution quality and runtime.",
author = "Marcus Randall and David Abramson",
year = "2001",
month = "11",
day = "1",
doi = "10.1023/A:1011211220465",
language = "English",
volume = "20",
pages = "185--210",
journal = "Computational Optimization and Applications",
issn = "0926-6003",
publisher = "Springer",
number = "2",

}

A general meta-heuristic based solver for combinatorial optimisation problems. / Randall, Marcus; Abramson, David.

In: Computational Optimization and Applications, Vol. 20, No. 2, 01.11.2001, p. 185-210.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - A general meta-heuristic based solver for combinatorial optimisation problems

AU - Randall, Marcus

AU - Abramson, David

PY - 2001/11/1

Y1 - 2001/11/1

N2 - In recent years, there have been many studies in which tailored heuristics and meta-heuristics have been applied to specific optimisation problems. These codes can be extremely efficient, but may also lack generality. In contrast, this research focuses on building a general-purpose combinatorial optimisation problem solver using a variety of meta-heuristic algorithms including Simulated Annealing and Tabu Search. The system is novel because it uses a modelling environment in which the solution is stored in dense dynamic list structures, unlike a more conventional sparse vector notation. Because of this, it incorporates a number of neighbourhood search operators that are normally only found in tailored codes and it performs well on a range of problems. The general nature of the system allows a model developer to rapidly prototype different problems. The new solver is applied across a range of traditional combinatorial optimisation problems. The results indicate that the system achieves good performance in terms of solution quality and runtime.

AB - In recent years, there have been many studies in which tailored heuristics and meta-heuristics have been applied to specific optimisation problems. These codes can be extremely efficient, but may also lack generality. In contrast, this research focuses on building a general-purpose combinatorial optimisation problem solver using a variety of meta-heuristic algorithms including Simulated Annealing and Tabu Search. The system is novel because it uses a modelling environment in which the solution is stored in dense dynamic list structures, unlike a more conventional sparse vector notation. Because of this, it incorporates a number of neighbourhood search operators that are normally only found in tailored codes and it performs well on a range of problems. The general nature of the system allows a model developer to rapidly prototype different problems. The new solver is applied across a range of traditional combinatorial optimisation problems. The results indicate that the system achieves good performance in terms of solution quality and runtime.

UR - http://www.scopus.com/inward/record.url?scp=0035501699&partnerID=8YFLogxK

U2 - 10.1023/A:1011211220465

DO - 10.1023/A:1011211220465

M3 - Article

VL - 20

SP - 185

EP - 210

JO - Computational Optimization and Applications

JF - Computational Optimization and Applications

SN - 0926-6003

IS - 2

ER -