LOCAL SEARCH TALK: 17 May, 6pm, City University, London,UK

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

Hi,

Details of the next Operational Research Society local search study group
meeting are below.

I look forward to seeing you there. The talk is open to all so feel free
to forward this onto anyone interested.

Andrew Tuson MA(Oxon) MSc(Edin) GRSC - Email: andrewt@soi.city.ac.uk

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

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

OR Society Local Search Study Group

Time: 		6pm (for 6.15pm) Wednesday 17th May 2000

Place: 		Room A529, Department of Computing, City University,
		Northampton Square, London, EC1V OHB.

Title:		Markov chain modelling of the solution surface in local search.

Speaker:	Prof. E.J. Anderson,

Affilation:	Australian Graduate School of Management
		The University of New South Wales

Abstract:

When local search methods are applied to combinatorial optimization
problems it is the characteristics of the solution surface that
determine the effectiveness of the method.  However surprisingly little
is known about the nature of the solution surface for such problems. 
This paper aims to advance our understanding of solution surface
characteristics.  The focus is on the basin of attraction associated
with each local minimum; that is the set of solutions from which a
particular local minimum is reached by following downhill local search. 

A Markov-chain model is proposed for the behaviour of the function
values occurring in a random walk on the solution surface.  The
probability transition matrix can be estimated and this is used to
estimate both the shape and the size of the basins of attraction.  In
order to test this approach a study is made of the problem of minimizing
weighted flowtime on unrelated parallel machines. 

For information on how to get to the venue please consult
http://www.soi.city.ac.uk/doc/findus.html, or contact Andrew Tuson on
020-7477-8164 (email: andrewt@soi.city.ac.uk).