SLIDE: A Useful Special Case of the CARDPATH Constraint

Abstract : We study the CARDPATH constraint. This ensures a given constraint holds a number of times down a sequence of variables. We show that SLIDE, a special case of CARDPATH where the slid constraint must hold always, can be used to encode a wide range of sliding sequence constraints including CARDPATH itself. We con- sider how to propagate SLIDE and provide a complete propagator for CARDPATH. Since propagation is NP-hard in general, we identify special cases where propagation takes polynomial time. Our experi- ments demonstrate that using SLIDE to encode global constraints can be as efficient and effective as specialised propagators.
Document type :
Conference papers
Complete list of metadatas

Cited literature [21 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00329876
Contributor : Christian Bessiere <>
Submitted on : Monday, October 13, 2008 - 3:27:48 PM
Last modification on : Saturday, October 12, 2019 - 7:26:08 PM

Identifiers

  • HAL Id : lirmm-00329876, version 1

Collections

Citation

Christian Bessière, Emmanuel Hébrard, Brahim Hnich, Zeynep Kiziltan, Toby Walsh. SLIDE: A Useful Special Case of the CARDPATH Constraint. ECAI: European Conference on Artificial Intelligence, Jul 2008, Patras, Greece. pp.475-479. ⟨lirmm-00329876⟩

Share

Metrics

Record views

148

Files downloads

3