We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Parallel Integer Optimization for Crew Scheduling.
- Authors
Alefragis, Panayiotis; Sanders, Peter; Takkula, Tuomo; Wedelin, Dag
- Abstract
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öteborg, Sweden, based on distributing the variables. A lazy variant of this approach which decouples communication and computation is even useful on networks of workstations. Furthermore, we develop a new sequential active set strategy which requires less work and is better adapted to the memory hierarchy properties of modem RISC processors. This algorithm is also suited for parallelization on a moderate number of networked workstations.
- Subjects
MATHEMATICAL optimization; LAGRANGIAN functions; MATHEMATICAL analysis; SEQUENTIAL analysis; MATHEMATICAL statistics; RISC microprocessors
- Publication
Annals of Operations Research, 2000, Vol 99, Issue 1-4, p141
- ISSN
0254-5330
- Publication type
Article
- DOI
10.1023/A:1019293017474