Abstract | ||
---|---|---|
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. |
Year | DOI | Venue |
---|---|---|
2012 | 10.1145/2245276.2245294 | SAC |
Keywords | Field | DocType |
neighbour evaluation,solution neighbourhood,nurse scheduling instance,useful automaton constraint,neighbourhood evaluation,constraint-directed local search,constant-time algorithm,chosen constraint,local search,computer science,computational complexity,controllability | Constraint satisfaction,Mathematical optimization,Constraint (mathematics),Computer science,Constraint programming,Constraint graph,Nurse scheduling problem,Constraint learning,Local search (optimization),Hybrid algorithm (constraint satisfaction) | Conference |
Citations | PageRank | References |
0 | 0.34 | 6 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Jun He | 1 | 0 | 0.34 |
Pierre Flener | 2 | 533 | 50.28 |
Justin Pearson | 3 | 20 | 3.44 |