An Optimal Arc Consistency Algorithm for a Chain of Atmost Constraints with Cardinality

Mohamed Siala (1) , Emmanuel Hébrard (1) , Marie-José Huguet (1)

1 LAAS-MOGISA

The ATMOSTSEQCARD constraint is the conjunction of a cardinality constraint on a sequence of n variables and of n - q + 1 constraints ATMOST u on each subsequence of size q. This constraint is useful in car-sequencing and crew-rostering problems. In [18], two algorithms designed for the AMONGSEQ constraint were adapted to this constraint with a O(2^q n) and O(n^3) worst case time complexity, respectively. In [10], another algorithm with a O(n2 log n) worst case time complexity and similarly adaptable to filter ATMOSTSEQCARD in O(n log n) was proposed. In this paper, we introduce an algorithm for achieving Arc Consistency on the ATMOSTSEQCARD constraint with a O(n) (hence optimal) worst case time complexity. We then empirically study the efficiency of our propagator on instances of the car-sequencing and crew-rostering problems.

Domaines: Intelligence artificielle [cs.AI]; Recherche opérationnelle [math.OC]

Mohamed Siala, Emmanuel Hébrard, Marie-José Huguet. An Optimal Arc Consistency Algorithm for a Chain of Atmost Constraints with Cardinality. Eighteenth International Conference on Principles and Practice of Constraint Programming, Oct 2012, Quebec, Canada. pp.55-69, ⟨10.1007/978-3-642-33558-7_7⟩. ⟨hal-00713860⟩