ISSN:
1572-9338
Keywords:
airline crew scheduling
;
combinatorial optimization
;
Lagrangian relaxation
;
memory hierarchy
;
parallel 0/1 integer linear programming
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
,
Economics
Notes:
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 modern RISC processors. This algorithm is also suited for parallelization on a moderate number of networked workstations.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1023/A:1019293017474
Permalink