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. 

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.

