Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
A Local Search System for Solving Constraint Problems of Declarative Graph-Based Global Constraints
RISE, Swedish ICT, SICS. IAM.
Number of Authors: 5
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, Springer , 2005, 1, , 308 p.166-184 p.Conference paper, Published paper (Refereed)
Abstract [en]

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.

Place, publisher, year, edition, pages
Springer , 2005, 1. , 308 p.166-184 p.
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:ri:diva-22899DOI: 10.1007/11415763_11ISBN: 3540255605 (print)OAI: oai:DiVA.org:ri-22899DiVA: diva2:1042464
Conference
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
Note
Published by Springer: Revised Selected Papers. Lecture Notes in Artificial Intelligence Vol. 3392 ISBN: 978-3-540-25560-4Available from: 2016-10-31 Created: 2016-10-31Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textDOI
By organisation
SICS
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar

Altmetric score

CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
v. 2.27.0