Speaker: Prof. Mark Wallace, OPTIMA

Minimal Conditions for Beneficial Local Search

Why does local search work?  Why is it beneficial, when solving a problem, to search in the neighbourhood of a current solution?  Such local improvement is a component of a wide variety of algorithms.  We elicit a minimal set of properties of problems and neighbourhoods that support two novel proofs that neighbourhood search is beneficial over blind search.  To explore the practical impact of these properties, a range of problem sets and neighbourhoods are generated, where these properties are satisfied to different degrees.  Experiments reveal that the benefits of neighbourhood search vary dramatically in consequence.

Mark Wallace has for many years explored the integration of different approaches to optimisation.  He led the ECLiPSE constraint programming platform team. ECLiPSe integrated commercial mathematical solvers, like Cplex; tree search, with propagation on discrete and continuous domains, and backtracking; as well as local search algorithms through its “tentative values” facility, which constraints could check and flag as inconsistent without causing backtracking.
He established the CTI-Monash Centre for Optimisation in travel, transport and logistics; he chairs the company Opturion, commercialising the G12 constraint programming platform; he is Editor-in-Chief of the Constraints journal and his latest book is “Building Decision Support Systems using MiniZinc”.

WED 20 OCTOBER 4PM – 5PM AEST

ZOOM MEETING ID: 873 1557 5255; PASSWORD: 778635

Event Flyer