Local Search Seminar and AGM: 20th November 2002 at 5.30pm, CityUniversity, London

[Andrew Tuson <andrewt@soi.city.ac.uk>]

All are welcome to this talk.

**********************************************************************

LOCAL SEARCH STUDY GROUP TALK (FOLLOWED BY AGM)

Title:	 Multilevel local search for combinatorial optimisation problems

Speaker: Chris Walshaw, University of Greenwich

Place:	 Room A529, Department of Computing, City University, 
	 Northampton Square, London EC1V 0HB

Time:	 Wednesday 20 November 2002 at 17.30. 

Abstract:

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 via multigrid solvers). However, with
the exception of graph partitioning, multilevel techniques have not been
widely applied to combinatorial problems. 

In this talk we address the use of multilevel ideas for such problems
where the refinement is carried out by local search algorithms 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 probable explanation for the
underlying process and extract some generic guidelines for its future use.

The AGM will follow the talk.