Loading
March 2007
Abstract:In the context of local search, we investigate the exploration of constraint-oriented neighbourhoods, where a set of constraints is picked before considering the neighbouring configurations where those constraints may have a different penalty. Given the semantics of a constraint, neighbourhoods consisting only of configurations with decreased (or preserved, or increased) penalty can be represented intensionally as a new attribute for constraint objects. We present a framework for combining neighbourhoods that allows different local search heuristics to be expressed, including multi-phase heuristics where an automatically identifiable suitable subset of the constraints is satisfied upon a first phase and then preserved in a second phase. This simplifies the design of local search algorithms compared to using just a variable-oriented neighbourhood, while not incurring any runtime overhead.
Available as PDF (262 kB, no cover)
Download BibTeX entry.