Time-Series Constraints: Improvements and Application in CP and MIP Contexts

Ekaterina Arafailova 1, 2 Nicolas Beldiceanu 1, 2 Rémi Douence 1, 3 Pierre Flener 4 María Andreína Francisco Rodríguez 4 Justin Pearson 4 Helmut Simonis 5
1 TASC - Theory, Algorithms and Systems for Constraints
Inria Rennes – Bretagne Atlantique , Département informatique - EMN, LINA - Laboratoire d'Informatique de Nantes Atlantique
3 ASCOLA - Aspect and composition languages
LINA - Laboratoire d'Informatique de Nantes Atlantique, Département informatique - EMN, Inria Rennes – Bretagne Atlantique
Abstract : A checker for a constraint on a variable sequence can often be compactly specified by an automaton, possibly with accumulators, that consumes the sequence of values taken by the variables; such an automaton can also be used to decompose its specified constraint into a conjunction of logical constraints. The inference achieved by this decomposition in a CP solver can be boosted by automatically generated implied constraints on the accumulators, provided the latter are updated in the automaton transitions by linear expressions. Automata with non-linear accumulator updates can be automatically synthesised for a large family of time-series constraints. In this paper, we describe and evaluate extensions to those techniques. First, we improve the automaton synthesis to generate automata with fewer accumulators. Second, we decompose a constraint specified by an automaton with accumulators into a conjunction of linear inequalities, for use by a MIP solver. Third, we generalise the implied constraint generation to cover the entire family of time-series constraints. The newly synthesised automata for time-series constraints outperform the old ones, for both the CP and MIP decompositions, and the generated implied constraints boost the inference, again for both the CP and MIP decompositions. We evaluate CP and MIP solvers on a prototypical application modelled using time-series constraints.
Type de document :
Communication dans un congrès
Claude-Guy Quimper. CPAIOR 2016 - 13th International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming , May 2016, Banff, Canada. Springer, 9676, pp.18-34, 2016, Lecture Notes in Computer Science. 〈https://symposia.cirrelt.ca/CPAIOR2016/en〉. 〈10.1007/978-3-319-33954-2〉
Liste complète des métadonnées

Littérature citée [14 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01355262
Contributeur : Ekaterina Arafailova <>
Soumis le : jeudi 22 septembre 2016 - 11:30:29
Dernière modification le : vendredi 22 juin 2018 - 09:29:51

Fichier

CPAIOR16.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Ekaterina Arafailova, Nicolas Beldiceanu, Rémi Douence, Pierre Flener, María Andreína Francisco Rodríguez, et al.. Time-Series Constraints: Improvements and Application in CP and MIP Contexts. Claude-Guy Quimper. CPAIOR 2016 - 13th International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming , May 2016, Banff, Canada. Springer, 9676, pp.18-34, 2016, Lecture Notes in Computer Science. 〈https://symposia.cirrelt.ca/CPAIOR2016/en〉. 〈10.1007/978-3-319-33954-2〉. 〈hal-01355262〉

Partager

Métriques

Consultations de la notice

508

Téléchargements de fichiers

94