1998
Tobias Müller
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.
Proceedings of the Sixth International Conference on the Practical Application of Prolog and the Forth International Conference on the Practical Application of Constraint Technology – PAPPACT98, Mar 1998, The Practical Application Company Ltd