The Increasing Nvalue Constraint

Nicolas Beldiceanu 1 Fabien Hermenier 2, 3 Xavier Lorca 1 Thierry Petit 1
1 TASC - Theory, Algorithms and Systems for Constraints
LINA - Laboratoire d'Informatique de Nantes Atlantique, Département informatique - EMN, Inria Rennes – Bretagne Atlantique
3 ASCOLA - Aspect and composition languages
LINA - Laboratoire d'Informatique de Nantes Atlantique, Département informatique - EMN, Inria Rennes – Bretagne Atlantique
Abstract : This paper introduces the Increasing_Nvalue constraint, which restricts the number of distinct values assigned to a sequence of variables so that each variable in the sequence is less than or equal to its successor. This constraint is a specialization of the Nvalue constraint, motivated by symmetry breaking. Propagating the Nvalue constraint is known as an NP-hard problem. However, we show that the chain of non strict inequalities on the variables makes the problem polynomial. We propose an algorithm achieving generalized arc-consistency in O(ΣDi) time, where ΣDi is the sum of domain sizes. This algorithm is an improvement of filtering algorithms obtained by the automaton-based or the Slide-based reformulations. We evaluate our constraint on a resource allocation problem.
Type de document :
Communication dans un congrès
Andrea Lodi and Michela Milano and Paolo Toth. Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, Jun 2010, Bologna, Italy. Springer, 6140, 2010, <10.1007/978-3-642-13520-0_5>
Liste complète des métadonnées

https://hal.inria.fr/hal-00915800
Contributeur : Contraintes Lina <>
Soumis le : lundi 9 décembre 2013 - 12:47:45
Dernière modification le : lundi 5 octobre 2015 - 17:00:10

Identifiants

Citation

Nicolas Beldiceanu, Fabien Hermenier, Xavier Lorca, Thierry Petit. The Increasing Nvalue Constraint. Andrea Lodi and Michela Milano and Paolo Toth. Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, Jun 2010, Bologna, Italy. Springer, 6140, 2010, <10.1007/978-3-642-13520-0_5>. <hal-00915800>

Partager

Métriques

Consultations de la notice

209