Search: id:"swepub:oai:DiVA.org:ri-22899" >
A Local Search Syst...
A Local Search System for Solving Constraint Problems of Declarative Graph-Based Global Constraints
-
- Bohlin, Markus (author)
- RISE,SICS
-
(creator_code:org_t)
- 1
- Berlin, Heidelberg : Springer, 2005
- 2005
- English.
-
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: Revised Selected Papers. - Berlin, Heidelberg : Springer. - 3540255605 ; , s. 166-184
- Related links:
-
http://DOI: 10.1007/...
-
show more...
-
https://urn.kb.se/re...
-
https://doi.org/10.1...
-
https://urn.kb.se/re...
-
show less...
Abstract
Subject headings
Close
- 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.
Subject headings
- NATURVETENSKAP -- Data- och informationsvetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences (hsv//eng)
Publication and Content Type
- ref (subject category)
- kon (subject category)
Find in a library
To the university's database