Automatically detecting neighbourhood constraint interactions using Comet

A. Andrew, J. Levine, Y. Naveh (Editor), P. Flener (Editor)

Research output: Contribution to conferencePaper

Abstract

Local Search has been shown to be capable of producing high quality solutions in a variety of hard constraint and optimisation problems. Typically implementing a Local Search algorithm is done in a problem specic manner. In the last few years a variety of approaches have emerged focussed on easing the implementation and creating a clean separation between the algorithm and problem. We present a system which can deduce information about the interactions between problem constraints and the search neighbourhoods whilst maintaining a loose coupling between these components. We apply this technique to the International Timetabling Competition instances and show an implementation expressed in Comet.

Conference

Conference5th International Workshop on Local Search Techniques in Constraint Satisfaction
CountryAustralia
CitySydney
Period15/09/08 → …

Fingerprint

Local search (optimization)

Keywords

  • Comet
  • neighbourhood constraint interactions
  • local search
  • constraint satisfaction

Cite this

Andrew, A., Levine, J., Naveh, Y. (Ed.), & Flener, P. (Ed.) (2008). Automatically detecting neighbourhood constraint interactions using Comet. 7-12. Paper presented at 5th International Workshop on Local Search Techniques in Constraint Satisfaction, Sydney, Australia.
Andrew, A. ; Levine, J. ; Naveh, Y. (Editor) ; Flener, P. (Editor). / Automatically detecting neighbourhood constraint interactions using Comet. Paper presented at 5th International Workshop on Local Search Techniques in Constraint Satisfaction, Sydney, Australia.6 p.
@conference{c09350ec5e0c45e7b84e4c0f3f65a4d5,
title = "Automatically detecting neighbourhood constraint interactions using Comet",
abstract = "Local Search has been shown to be capable of producing high quality solutions in a variety of hard constraint and optimisation problems. Typically implementing a Local Search algorithm is done in a problem specic manner. In the last few years a variety of approaches have emerged focussed on easing the implementation and creating a clean separation between the algorithm and problem. We present a system which can deduce information about the interactions between problem constraints and the search neighbourhoods whilst maintaining a loose coupling between these components. We apply this technique to the International Timetabling Competition instances and show an implementation expressed in Comet.",
keywords = "Comet, neighbourhood constraint interactions, local search, constraint satisfaction",
author = "A. Andrew and J. Levine and Y. Naveh and P. Flener",
year = "2008",
month = "9",
day = "1",
language = "English",
pages = "7--12",
note = "5th International Workshop on Local Search Techniques in Constraint Satisfaction ; Conference date: 15-09-2008",

}

Andrew, A, Levine, J, Naveh, Y (ed.) & Flener, P (ed.) 2008, 'Automatically detecting neighbourhood constraint interactions using Comet' Paper presented at 5th International Workshop on Local Search Techniques in Constraint Satisfaction, Sydney, Australia, 15/09/08, pp. 7-12.

Automatically detecting neighbourhood constraint interactions using Comet. / Andrew, A.; Levine, J.; Naveh, Y. (Editor); Flener, P. (Editor).

2008. 7-12 Paper presented at 5th International Workshop on Local Search Techniques in Constraint Satisfaction, Sydney, Australia.

Research output: Contribution to conferencePaper

TY - CONF

T1 - Automatically detecting neighbourhood constraint interactions using Comet

AU - Andrew, A.

AU - Levine, J.

A2 - Naveh, Y.

A2 - Flener, P.

PY - 2008/9/1

Y1 - 2008/9/1

N2 - Local Search has been shown to be capable of producing high quality solutions in a variety of hard constraint and optimisation problems. Typically implementing a Local Search algorithm is done in a problem specic manner. In the last few years a variety of approaches have emerged focussed on easing the implementation and creating a clean separation between the algorithm and problem. We present a system which can deduce information about the interactions between problem constraints and the search neighbourhoods whilst maintaining a loose coupling between these components. We apply this technique to the International Timetabling Competition instances and show an implementation expressed in Comet.

AB - Local Search has been shown to be capable of producing high quality solutions in a variety of hard constraint and optimisation problems. Typically implementing a Local Search algorithm is done in a problem specic manner. In the last few years a variety of approaches have emerged focussed on easing the implementation and creating a clean separation between the algorithm and problem. We present a system which can deduce information about the interactions between problem constraints and the search neighbourhoods whilst maintaining a loose coupling between these components. We apply this technique to the International Timetabling Competition instances and show an implementation expressed in Comet.

KW - Comet

KW - neighbourhood constraint interactions

KW - local search

KW - constraint satisfaction

UR - http://sysrun.haifa.il.ibm.com/hrl/lscs2008/

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

M3 - Paper

SP - 7

EP - 12

ER -

Andrew A, Levine J, Naveh Y, (ed.), Flener P, (ed.). Automatically detecting neighbourhood constraint interactions using Comet. 2008. Paper presented at 5th International Workshop on Local Search Techniques in Constraint Satisfaction, Sydney, Australia.