3documents trouvés
An optimal arc consistency algorithm for a chain of atmost constraints with cardinality
M.SIALA, E.HEBRARD, M.J.HUGUET
MOGISA
Manifestation avec acte : International Conference on Principles and Practice of Constraint Programming (CP) 2012 du 08 octobre au 12 octobre 2012, Québec (Canada), Article primé "Honorable Mention", Octobre 2012, 15p. , N° 12343
Lien : http://hal.archives-ouvertes.fr/hal-00713860
Diffusable
Plus d'informations
Abstract
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.
A study of branching heuristics for the car-sequencing problem
M.SIALA, E.HEBRARD, M.J.HUGUET
MOGISA
Manifestation avec acte : International Workshop on Search Strategies and Non-standard Objectives (SSNOWorkshop'12), Nantes (France), 29 Mai 2012, 15p. , N° 12287
Diffusable
127405Algorithme optimal d'arc-consistance pour une séquence de contraintes AtMost avec cardinalité
E.HEBRARD, M.J.HUGUET, M.SIALA
MOGISA
Manifestation avec acte : Journées Francophones de Programmation par Contraintes (JFPC'2012), Toulouse (France), 22-24 Mai 2012, 10p. , N° 12288
Diffusable
127407