Name
Title | ||
|---|---|---|
A local search system for solving constraint problems of declarative graph-based global constraints |
Abstract | ||
|---|---|---|
In this paper we present a local search constraint solver in which constraints are expressed using cost functions on graph structures of filter constraints of equal type. A similar theoretical approach has previously been used to model a large number of complex global constraints, which motivates the use of such a model in practice. In a local search context, we view global constraints as complex cost functions, encapsulating the structure of the constraints using a graph of variables, values and filter constraints. This representation gives us a declarative model, which can also be used to efficiently compute a cost as well as conflict levels of the variables in the constraints. We have implemented these ideas in a compositional C++ framework called Composer, which can be used to solve systems of graph-based constraints. We demonstrate the usability of this approach on several well-known global constraints, and show by experimental results on two problems that an approach using a graph basis for global constraint modeling is not only possible in practice, but also competitive with existing constraint-based local search systems. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1007/11415763_11 | Lecture Notes in Computer Science |
Keywords | Field | DocType |
graph basis,graph structure,declarative graph-based global constraint,declarative model,constraint-based local search system,global constraint,global constraint modeling,cost function,constraint problem,complex cost function,complex global constraint,well-known global constraint,local search | Constraint satisfaction,Mathematical optimization,Local consistency,Constraint (mathematics),Computer science,Constraint programming,Constraint graph,Constraint satisfaction problem,Constrained clustering,Local search (optimization) | Conference |
Volume | ISSN | ISBN |
3392 | 0302-9743 | 3-540-25560-5 |
Citations | PageRank | References |
0 | 0.34 | 13 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Markus Bohlin | 1 | 77 | 14.24 |