zbMATH — the first resource for mathematics

Sequencing and counting with the multicost-regular constraint. (English) Zbl 1241.68104
van Hoeve, Willem-Jan (ed.) et al., Integration of AI and OR techniques in constraint programming for combinatorial optimization problems. 6th international conference, CPAIOR 2009, Pittsburgh, PA, USA, May 27–31, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-01928-9/pbk). Lecture Notes in Computer Science 5547, 178-192 (2009).
Summary: This paper introduces a global constraint encapsulating a regular constraint together with several cumulative costs. It is motivated in the context of personnel scheduling problems, where a schedule meets patterns and occurrence requirements which are intricately bound. The optimization problem underlying the multicost-regular constraint is NP-hard but it admits an efficient Lagrangian relaxation. Hence, we propose a filtering based on this relaxation. The expressiveness and the efficiency of this new constraint is experimented on personnel scheduling benchmark instances with standard work regulations. The comparative empirical results show how multicost-regular can significantly outperform a decomposed model with regular and global-cardinality constraints.
For the entire collection see [Zbl 1163.68006].

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
90C27 Combinatorial optimization
Full Text: DOI