We consider the multilevel paradigm and its potential to aid the solution of
combinatorial optimisation problems. The multilevel paradigm involves recursive
coarsening to create a hierarchy of approximations to the original problem. An
initial solution is found (sometimes for the original problem, sometimes at the
coarsest level) and then iteratively refined at each level, coarsest to finest.
As a general solution strategy the multilevel procedure has been in use for
many years and has been applied to many problem areas (most notably multigrid).
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
meta-heuristic. The results provide compelling evidence that, although the
multilevel framework cannot be considered as a panacea for combinatorial
problems, it can provide a valuable 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.
Speaker bio
Presentation (PDF File)
Copyright. All Rights Reserved.