Solution neighbourhoods for constraint-directed local search
Jun He, Pierre Flener, Justin Pearson · 2012
We propose solution neighbourhoods, which contain only solutions to a chosen constraint, as the solutions to a constraint capture the structure of the constraint. We save the time needed for neighbourhood evaluation of that constraint by using a solution neighbourhood. This may be useful especially for constraints for which there exists no known constant-time algorithm for neighbour evaluation. We design a solution neighbourhood for the very useful automaton constraint, and demonstrate the practicality of our approach on a library of nurse scheduling instances. We show the feasibility of designing solution neighbourhoods for other constraints.