Name
Abstract | ||
|---|---|---|
In constraint-based local search the solutions are described declaratively by a conjunction of (often high-level) constraints. In this article we show that this opens up new ideas for constraint-directed search. For a constraint we introduce three neighbourhoods, where the penalty for that constraint alone is decreasing, increasing, or unchanged. We give specialised algorithms for common constraints that efficiently implement these neighbourhoods. Further, we give a general algorithm that implements these neighbourhoods from specifications of constraints in monadic existential second-order logic. Finally, we show how common constraint-directed local search algorithms are often easier to express using these neighbourhoods. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1016/j.ic.2008.12.001 | Inf. Comput. |
Keywords | Field | DocType |
constraint-directed search,monadic existential second-order logic,common constraint,specialised algorithm,general algorithm,constraint-based local search,common constraint-directed local search,new idea,local search,second order,computer science,local search algorithm | Search algorithm,General algorithm,Artificial intelligence,Local search (optimization),Mathematics,Monad (functional programming),Information and Computer Science,Penalty method | Journal |
Volume | Issue | ISSN |
207 | 3 | Information and Computation |
Citations | PageRank | References |
3 | 0.46 | 10 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Magnus Ågren | 1 | 72 | 8.03 |
| Pierre Flener | 2 | 533 | 50.28 |
| Justin Pearson | 3 | 237 | 24.28 |