# Multilevel refinement for combinatorial optimisation: boosting metaheuristic performance

Walshaw, Chris (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)

## 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 |

School / Department / Research Groups: | School of Computing & Mathematical Sciences |

Related URLs: | |

Last Modified: | 10 May 2013 14:40 |

URI: | http://gala.gre.ac.uk/id/eprint/1259 |

### Actions (login required)

View Item |