SODA

Inferring variable conflicts for local search

Ågren, Magnus and Flener, Pierre and Pearson, Justin (2006) Inferring variable conflicts for local search. In: Proceedings of CP'06, 24-29 Sept 2006, Nantes, France.

Full text not available from this repository.

Official URL: http://dx.doi.org/10.1007/11889205_47

Abstract

For efficiency reasons, neighbourhoods in local search are often shrunk by only considering moves modifying variables that actually contribute to the overall penalty. These are known as conflicting variables. We propose a new definition for measuring the conflict of a variable in a model and apply it to the set variables of models expressed in existential second-order logic extended with counting (EMSO). Such a variable conflict can be automatically and incrementally evaluated. Furthermore, this measure is lower-bounded by an intuitive conflict measure, and upper-bounded by the penalty of the model. We also demonstrate the usefulness of the approach by replacing a built-in global constraint by an EMSO version thereof, while still obtaining competitive results.

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

Repository Staff Only: item control page