User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse




Conference Paper

High performance integer optimization for crew scheduling


Sanders,  Peter
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available

Sanders, P., Takkula, T., & Wedelin, D. (1999). High performance integer optimization for crew scheduling. In P. Sloot, M. Bubak, A. Hoekstra, & B. Hertzberger (Eds.), Proceedings of the 7th International Conference on High-Performance Computing and Networking Europe (HPCN Europe-99) (pp. 3-12). Berlin: Springer.

Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-35D2-3
Performance aspects of a Lagrangian relaxation based heuristic for solving large 0-1 integer linear programs are discussed. In particular, we look at its application to airline and railway crew scheduling problems. We present a scalable parallelization of the original algorithm used in production at Carmen Systems AB, G\"oteborg, Sweden, based on distributing the variables and a new sequential \emph{active set strategy} which requires less work and is better adapted to the memory hierachy properties of modern RISC processors. The active set strategy can even be parallelized on networks of workstations.