Revisiting constraint-directed search

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