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

23 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 Sep 2008

Fingerprint

Detectors

Keywords

  • Comet
  • local search
  • neighbourhood constraint interactions

Cite this

Andrew, A., Stergiou, K. (Ed.), & Yap, R. (Ed.) (2008). Automatically detecting neighbourhood constraint interactions using comet. In Proceedings of the CP 2008 Doctoral Programme (pp. 7-12)
Andrew, A. ; Stergiou, K. (Editor) ; Yap, R. (Editor). / Automatically detecting neighbourhood constraint interactions using comet. Proceedings of the CP 2008 Doctoral Programme. 2008. pp. 7-12
@inproceedings{bf0267b26d444d958a46f70f279240b0,
title = "Automatically detecting neighbourhood constraint interactions using comet",
abstract = "The major benet of using events as the basis for our detection system isthe clean separation between the neighbourhoods and detector which wecan achieve. The detector simply iterates over a set of Neighbourhoodobjects and checks each for interactions. The acceptance function for theneighbourhood is set to accept any tness. For purposes of detecting aninteraction it does not matter whether a move reduces or increases theconstraint violations; both indicate that a relationship exists.The simulation is performed in two stages. Starting from a randomlycreated initial solution a random move from the neighbourhood is chosen,often this will lead to a constraint change and prevent the need for furtherexploration. For some constraints the chance of randomly selecting amove which would violate it is fairly low and so a more rigourous searchis required. If the initial move has not found any interaction then thedetector explores every neighbouring state from the current position. Ifat any stage a change of the constraint violations is detected then theexploration is stopped.",
keywords = "Comet, local search, neighbourhood constraint interactions",
author = "A. Andrew and K. Stergiou and R. Yap",
year = "2008",
month = "9",
day = "1",
language = "English",
pages = "7--12",
booktitle = "Proceedings of the CP 2008 Doctoral Programme",

}

Andrew, A, Stergiou, K (ed.) & Yap, R (ed.) 2008, Automatically detecting neighbourhood constraint interactions using comet. in Proceedings of the CP 2008 Doctoral Programme. pp. 7-12.

Automatically detecting neighbourhood constraint interactions using comet. / Andrew, A.; Stergiou, K. (Editor); Yap, R. (Editor).

Proceedings of the CP 2008 Doctoral Programme. 2008. p. 7-12.

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

TY - GEN

T1 - Automatically detecting neighbourhood constraint interactions using comet

AU - Andrew, A.

A2 - Stergiou, K.

A2 - Yap, R.

PY - 2008/9/1

Y1 - 2008/9/1

N2 - The major benet of using events as the basis for our detection system isthe clean separation between the neighbourhoods and detector which wecan achieve. The detector simply iterates over a set of Neighbourhoodobjects and checks each for interactions. The acceptance function for theneighbourhood is set to accept any tness. For purposes of detecting aninteraction it does not matter whether a move reduces or increases theconstraint violations; both indicate that a relationship exists.The simulation is performed in two stages. Starting from a randomlycreated initial solution a random move from the neighbourhood is chosen,often this will lead to a constraint change and prevent the need for furtherexploration. For some constraints the chance of randomly selecting amove which would violate it is fairly low and so a more rigourous searchis required. If the initial move has not found any interaction then thedetector explores every neighbouring state from the current position. Ifat any stage a change of the constraint violations is detected then theexploration is stopped.

AB - The major benet of using events as the basis for our detection system isthe clean separation between the neighbourhoods and detector which wecan achieve. The detector simply iterates over a set of Neighbourhoodobjects and checks each for interactions. The acceptance function for theneighbourhood is set to accept any tness. For purposes of detecting aninteraction it does not matter whether a move reduces or increases theconstraint violations; both indicate that a relationship exists.The simulation is performed in two stages. Starting from a randomlycreated initial solution a random move from the neighbourhood is chosen,often this will lead to a constraint change and prevent the need for furtherexploration. For some constraints the chance of randomly selecting amove which would violate it is fairly low and so a more rigourous searchis required. If the initial move has not found any interaction then thedetector explores every neighbouring state from the current position. Ifat any stage a change of the constraint violations is detected then theexploration is stopped.

KW - Comet

KW - local search

KW - neighbourhood constraint interactions

UR - http://www.cis.strath.ac.uk/cis/research/publications/papers/strath_cis_publication_2280.pdf

UR - http://ww2.cs.mu.oz.au/cp2008/DP%20proceedings.pdf

M3 - Conference contribution book

SP - 7

EP - 12

BT - Proceedings of the CP 2008 Doctoral Programme

ER -

Andrew A, Stergiou K, (ed.), Yap R, (ed.). Automatically detecting neighbourhood constraint interactions using comet. In Proceedings of the CP 2008 Doctoral Programme. 2008. p. 7-12