Bohlin, Markus (2005) A Local Search System for Solving Constraint Problems of Declarative Graph-Based Global Constraints. In: Applications of Declarative Programming and Knowledge Management: 15th International Conference on Applications of Declarative Programming and Knowledge Management, INAP 2004, and 18th Workshop on Logic Programming, 4-6 March 2004, Potsdam, Germany.
Full text not available from this repository.
Official URL: DOI: 10.1007/11415763_11
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.
|Item Type:||Conference or Workshop Item (Paper)|
|Additional Information:||Published by Springer: Revised Selected Papers. Lecture Notes in Artificial Intelligence Vol. 3392 ISBN: 978-3-540-25560-4|
|Deposited By:||IAM Researcher|
|Deposited On:||17 Jun 2009|
|Last Modified:||18 Nov 2009 16:22|
Repository Staff Only: item control page