Walshaw, Chris ORCID: 0000-0003-0253-7779 (2004) Multilevel refinement for combinatorial optimisation problems. Annals of Operations Research, 131 (1-4). pp. 325-372. ISSN 0254-5330 (Print), 1572-9338 (Online) (doi:https://doi.org/10.1023/B:ANOR.0000039525.80601.15)

Full text not available from this repository.

Abstract

We consider the multilevel paradigm and its potential to aid the solution of combinatorial optimisation problems. The multilevel paradigm is a simple one, which involves recursive coarsening to create a hierarchy of approximations to the original problem. An initial solution is found (sometimes for the original problem, sometimes the coarsest) and then iteratively refined at each level. As a general solution strategy, the multilevel paradigm has been in use for many years and has been applied to many problem areas (most notably in the form of multigrid techniques). However, with the exception of the graph partitioning problem, multilevel techniques have not been widely applied to combinatorial optimisation problems. In this paper we address the issue of multilevel refinement for such problems and, with the aid of examples and results in graph partitioning, graph colouring and the travelling salesman problem, make a case for its use as a metaheuristic. The results provide compelling evidence that, although the multilevel framework cannot be considered as a panacea for combinatorial problems, it can provide an extremely useful addition to the combinatorial optimisation toolkit. We also give a possible explanation for the underlying process and extract some generic guidelines for its future use on other combinatorial problems.

Item Type:	Article
Additional Information:	[1] CMS Ref. No: 04/30.
Uncontrolled Keywords:	multilevel refinement, combinatorial optimisation, metaheuristic, graph partitioning, travelling salesman, graph colouring
Subjects:	Q Science > QA Mathematics
Pre-2014 Departments:	School of Computing & Mathematical Sciences School of Computing & Mathematical Sciences > Computer & Computational Science Research Group School of Computing & Mathematical Sciences > Department of Computer Science School of Computing & Mathematical Sciences > Department of Mathematical Sciences
Related URLs:	Publisher Publisher Organisation
Last Modified:	14 Oct 2016 09:02
URI:	http://gala.gre.ac.uk/id/eprint/807

Actions (login required)

View Item