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
Weakly Monotonic Propagators
KTH, School of Information and Communication Technology (ICT), Communication: Services and Infrastucture (Closed 20120101), Software and Computer Systems, SCS (Closed 20120101).ORCID iD: 0000-0002-6283-7004
2009 (English)In: PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING / [ed] Gent IP, 2009, Vol. 5732, 723-730 p.Conference paper, Published paper (Refereed)
Abstract [en]

Today's models for propagation-based constraint solvers require propagators as implementations of constraints to be at least contracting and monotonic. These models do not comply with reality: today's constraint, programming systems actually use non-monotonic propagators. This paper introduces the first realistic model of constraint propagation by assuming it propagator to be weakly monotonic (complying with the constraint it implements). Weak monotonicity is shown to be the minimal property that guarantees constraint propagation to be sound and complete. The important insight is that weak monotonicity makes propagation in combination. with search well behaved. A case study suggests that non-monotonicity call be seen as all opportunity for more efficient propagation.

Place, publisher, year, edition, pages
2009. Vol. 5732, 723-730 p.
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 5732
Keyword [en]
Constraint programming systems, Constraint propagation, Constraint solvers, Minimal properties, Monotonicity, Non-monotonicity, Realistic model, Computer programming
National Category
Computer Science
Identifiers
URN: urn:nbn:se:kth:diva-30347DOI: 10.1007/978-3-642-04244-7_56ISI: 000273241200053Scopus ID: 2-s2.0-70350413800ISBN: 978-3-642-04243-0 (print)OAI: oai:DiVA.org:kth-30347DiVA: diva2:401707
Conference
15th International Conference on Principles and Practice of Constraint Programming (CP 2009), Lisbon, PORTUGAL, SEP 20-24, 2009
Note

QC 20110303

Available from: 2011-03-03 Created: 2011-02-24 Last updated: 2016-05-25Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Authority records BETA

Schulte, Christian

Search in DiVA

By author/editor
Schulte, Christian
By organisation
Software and Computer Systems, SCS (Closed 20120101)
Computer Science

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 22 hits
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