Self-decomposable Global Constraints

Jean-Guillaume Fages (1, 2) , Xavier Lorca (1, 2) , Thierry Petit (2, 1)

1 TASC - Theory, Algorithms and Systems for Constraints
2 Mines Nantes - Mines Nantes

Scalability becomes more and more critical to decision support technologies. In order to address this issue in Constraint Programming, we introduce the family of self-decomposable constraints. These constraints can be satisfied by applying their own filtering algorithms on variable subsets only. We introduce a generic framework which dynamically decompose propagation, by filtering over variable subsets. Our experiments over the CUMULATIVE constraint illustrate the practical relevance of self-decomposition.

Domaines: Informatique [cs]; Intelligence artificielle [cs.AI]; Recherche opérationnelle [math.OC]; Mathématique discrète [cs.DM]

Jean-Guillaume Fages, Xavier Lorca, Thierry Petit. Self-decomposable Global Constraints. ECAI 2014, 21st International Conference on Artificial Intelligence, Aug 2014, Prague, Czech Republic. pp.297-302, ⟨10.3233/978-1-61499-419-0-297⟩. ⟨hal-01088964⟩