Walshaw, Chris ORCID: https://orcid.org/0000-0003-0253-7779 (2008) Multilevel refinement for combinatorial optimisation: boosting metaheuristic performance. In: Blum, Christian, Aguilera, Maria José Blesa, Roli, Andrea and Sampels, Michael, (eds.) Hybrid Metaheuristics: An Emerging Approach for Optimization. Studies in Computational Intelligence (114). Springer Berlin Heidelberg, Berlin / Heidelberg, Germany, pp. 261-289. ISBN 9783540782940 (doi:10.1007/978-3-540-78295-7_9)

Full text not available from this repository.

Abstract

The multilevel paradigm as applied to combinatorial optimisation problems is a simple one, which at its most basic involves recursive coarsening to create a hierarchy of approximations to the original problem. An initial solution is found, usually at the coarsest level, and then iteratively refined at each level, coarsest to finest, typically by using some kind of heuristic optimisation algorithm (either a problem-specific local search scheme or a metaheuristic). Solution extension (or projection) operators can transfer the solution from one level to another. As a general solution strategy, the multilevel paradigm has been in use for many years and has been applied to many problem areas (for example multigrid techniques can be viewed as a prime example of the paradigm). Overview papers such as [] attest to its efficacy. However, with the exception of the graph partitioning problem, multilevel techniques have not been widely applied to combinatorial problems and in this chapter we discuss recent developments. In this chapter we survey the use of multilevel combinatorial techniques and consider their ability to boost the performance of (meta)heuristic optimisation algorithms.

Item Type:	Book Section
Additional Information:	[1] ISBN: 978-3-540-78294-0 (Print), 978-3-540-78295-7 (Online). [2] Series ISSN: 1860-949X.
Uncontrolled Keywords:	multilevel paradigm, combinatorial optimisation, metaheuristic optimisation
Subjects:	Q Science > QA Mathematics
Pre-2014 Departments:	School of Computing & Mathematical Sciences
Related URLs:	Publisher Organisation
Last Modified:	14 Oct 2016 09:03
URI:	http://gala.gre.ac.uk/id/eprint/1259

Actions (login required)

View Item