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
View-based propagator derivation
KTH, School of Information and Communication Technology (ICT), Software and Computer systems, SCS.ORCID iD: 0000-0002-6283-7004
National ICT Australia (NICTA), Faculty of Information Technology, Monash Universit.
2013 (English)In: Constraints, ISSN 1383-7133, E-ISSN 1572-9354, Vol. 18, no 1, 75-107 p.Article in journal (Refereed) Published
Abstract [en]

When implementing a propagator for a constraint, one must decide about variants: When implementing min, should one also implement max Should one implement linear constraints both with unit and non-unit coefficients Constraint variants are ubiquitous: implementing them requires considerable (if not prohibitive) effort and decreases maintainability, but will deliver better performance than resorting to constraint decomposition. This paper shows how to use views to derive propagator variants, combining the efficiency of dedicated propagator implementations with the simplicity and effortlessness of decomposition. A model for views and derived propagators is introduced. Derived propagators are proved to be perfect in that they inherit essential properties such as correctness and domain and bounds consistency. Techniques for systematically deriving propagators such as transformation, generalization, specialization, and type conversion are developed. The paper introduces an implementation architecture for views that is independent of the underlying constraint programming system. A detailed evaluation of views implemented in Gecode shows that derived propagators are efficient and that views often incur no overhead. Views have proven essential for implementing Gecode, substantially reducing the amount of code that needs to be written and maintained.

Place, publisher, year, edition, pages
Springer, 2013. Vol. 18, no 1, 75-107 p.
Keyword [en]
Constraint propagation, Constraint solver implementation, Parametric propagators, Views
National Category
Computer Science
Identifiers
URN: urn:nbn:se:kth:diva-107405DOI: 10.1007/s10601-012-9133-zISI: 000312879500004Scopus ID: 2-s2.0-84871922124OAI: oai:DiVA.org:kth-107405DiVA: diva2:575808
Funder
Swedish Research Council, 621-2004-4953
Note

QC 20130115

Available from: 2012-12-11 Created: 2012-12-11 Last updated: 2017-12-07Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopusict.kth.se

Authority records BETA

Schulte, Christian

Search in DiVA

By author/editor
Schulte, Christian
By organisation
Software and Computer systems, SCS
In the same journal
Constraints
Computer Science

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 71 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