Publication details

Saarland University Computer Science

Solving Set Partitioning Problems with Constraint Programming

Tobias Müller

Proceedings of the Sixth International Conference on the Practical Application of Prolog and the Forth International Conference on the Practica, pp. 313--332, The Practical Application Company Ltd, March 1998

This paper investigates the potential of constraint programming for solving set partitioning problems occurring in crew scheduling, where constraint programming is restricted to not employ external solvers, as for instance integer linear programming solvers. We evaluate preprocessing steps known from the OR literature on moderately sized set partitioning problems. Further, we propose a new preprocessing technique which allows to reduce problem size more effectively than standard preprocessing techniques but with similar computational effort. Additionally, we propose a propagation algorithm for a global set partitioning constraint which, compared with other constraint programming approaches, finds and proves optimal solutions significantly faster resp. produces better solutions in a given time period.

Download PDF        Show BibTeX               


Login to edit


Webmaster, Wed Sep 16 10:47:00 2009