SODA

Revisiting constraint-directed search

Ågren, Magnus and Flener, Pierre and Pearson, Justin (2007) Revisiting constraint-directed search. In: Proceedings of LSCS'07, the 4th International Workshop on Local Search Techniques in Constraint Satisfaction, 23 Sept 2007, Providence, Rhode Island, USA.

Full text not available from this repository.

Abstract

We revisit the exploration of constraint-directed neighbourhoods, where a (small) set of constraints is picked before considering the neighbouring configurations where those constraints have a decreased (or preserved, or increased) penalty. Given the semantics of a constraint, such neighbourhoods can be represented via new attributes or primitives for the corresponding constraint object. We show how to define these neighbourhoods for set constraints, whether built-in or specified in monadic existential second-order logic. We also present an implementation of the corresponding primitives in our local search framework. Using these new primitives, we show how some common local-search algorithms are simplified, compared to using just a variable-directed neighbourhood, while not incurring any run-time overhead.

Item Type:Conference or Workshop Item (Paper)
ID Code:3690
Deposited By:Magnus Ņgren
Deposited On:12 Oct 2009
Last Modified:18 Nov 2009 16:26

Repository Staff Only: item control page