Loading ...
Sorry, an error occurred while loading the content.

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

Expand Messages
  • Andrew Tuson
    All are welcome to this talk. ********************************************************************** LOCAL SEARCH STUDY GROUP TALK (FOLLOWED BY AGM) Title:
    Message 1 of 1 , Nov 1 6:25 AM
    • 0 Attachment
      All are welcome to this talk.



      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.


      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.
    Your message has been successfully submitted and would be delivered to recipients shortly.