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
Inria Rennes – Bretagne Atlantique , Département informatique - EMN, LINA - Laboratoire d'Informatique de Nantes Atlantique
3 ASCOLA - Aspect and composition languages
Inria Rennes – Bretagne Atlantique , Département informatique - EMN, LINA - Laboratoire d'Informatique de Nantes 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.
Complete list of metadatas

https://hal.inria.fr/hal-00915800
Contributor : Contraintes Lina <>
Submitted on : Monday, December 9, 2013 - 12:47:45 PM
Last modification on : Friday, June 22, 2018 - 9:31:57 AM

Links full text

Identifiers

Citation

Nicolas Beldiceanu, Fabien Hermenier, Xavier Lorca, Thierry Petit. The Increasing Nvalue Constraint. Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, Jun 2010, Bologna, Italy. ⟨10.1007/978-3-642-13520-0_5⟩. ⟨hal-00915800⟩

Share

Metrics

Record views

315