Technical Report 2006-005

Inferring Variable Conflicts for Local Search from High-Level Models

Magnus Ågren, Pierre Flener, and Justin Pearson

February 2006

For efficiency reasons, neighbourhoods in local search algorithms are often shrunk by only considering moves modifying variables that actually contribute to the overall penalty. These are known as conflicting variables. This is a well-known technique for speeding up search. State-of-the-art solutions to, e.g., the progressive party problem exploit this with great success. We propose a way of automatically and incrementally measuring the conflict of a variable in a local search model and apply this to the set variables of models expressed in existential second-order logic extended with counting (ESOL+). Furthermore, we show that 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 a modelled ESOL+ version thereof, while still obtaining competitive results. This is especially attractive when a particular (global) constraint is not built in.

Note: Updated March 2006

Available as PDF (223 kB, no cover) and PDF (218 kB)

Download BibTeX entry.