LOCAL SEARCH TALK: 20th Oct 2000 @ 3pm, Essex Univ, UK

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

Dear all,

This may be of interest to some of you. I hope to see you there.

Dr Andrew Tuson MA(Oxon) MSc(Edin) PhD(Edin) GRSC (andrewt@soi.city.ac.uk)

Lecturer, Department of Computing, City University, London, UK.

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

Local Search Study Group

Friday, 20 October at 3pm

Room 4B.531, Department of Computer Science, University of Essex

Local Search using Neighborhoods of Exponential Size

Chris N. Potts
University of Southampton

Abstract

A new neighborhood search technique is introduced that uses dynamic
programming to search an exponential size neighborhood in polynomial
time.  This technique is called dynasearch.  We apply dynasearch to
three types of sequencing problems; the total weighted tardiness
scheduling problem, the linear ordering problem and the traveling
salesman problem.  Computational results show that, for restarts close
to previous local minima, dynasearch is significantly more effective
than classical first improve or best improve descent.  As a consequence,
our proposed algorithms use dynsearch with an iterated local search
framework, where each descent is started a few random moves away from
previous local minima.  Computational results show that the proposed
dynasearch algorithms are more effective than other known local search
heuristics for the total weighted tardiness problem and for the linear
ordering problem, and are competitive with other methods for the
traveling salesman problem.