Automatically detecting neighbourhood constraint interactions using comet

A. Andrew, K. Stergiou (Editor), R. Yap (Editor)

Research output: Chapter in Book/Report/Conference proceedingConference contribution book

59 Downloads (Pure)

Abstract

The major benet of using events as the basis for our detection system is
the clean separation between the neighbourhoods and detector which we
can achieve. The detector simply iterates over a set of Neighbourhood
objects and checks each for interactions. The acceptance function for the
neighbourhood is set to accept any tness. For purposes of detecting an
interaction it does not matter whether a move reduces or increases the
constraint violations; both indicate that a relationship exists.
The simulation is performed in two stages. Starting from a randomly
created initial solution a random move from the neighbourhood is chosen,
often this will lead to a constraint change and prevent the need for further
exploration. For some constraints the chance of randomly selecting a
move which would violate it is fairly low and so a more rigourous search
is required. If the initial move has not found any interaction then the
detector explores every neighbouring state from the current position. If
at any stage a change of the constraint violations is detected then the
exploration is stopped.
Original languageEnglish
Title of host publicationProceedings of the CP 2008 Doctoral Programme
Pages7-12
Number of pages6
Publication statusPublished - 1 Sept 2008

Keywords

  • Comet
  • local search
  • neighbourhood constraint interactions

Fingerprint

Dive into the research topics of 'Automatically detecting neighbourhood constraint interactions using comet'. Together they form a unique fingerprint.

Cite this