SODA

A Local Search System for Solving Constraint Problems of Declarative Graph-Based Global Constraints

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

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.

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
ID Code:3416
Deposited By:IAM Researcher
Deposited On:17 Jun 2009
Last Modified:18 Nov 2009 16:22

Repository Staff Only: item control page