logo
CanyamAI summaries for academic research
language
MobileMobile
  • Phone FeatureWeChat Mini Program
EnglishEnglish
noticeNotice
BlogBlog
delete
arrow
Return

Parallel integer optimization for crew scheduling

delete2000-01-01
delete15
PRE
AI
P
Panayiotis Alefragis
P
Peter Sanders
T
Tuomo Takkula
D
Dag Wedelin
DOI：10.1023/A:1019293017474delete
deleteOriginal
deleteOriginal request for help
deleteShare
deleteSave
Abstract

Abstract

En 中文
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, Goteborg, 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.
Keywords:
airline crew scheduling
combinatorial optimization
Lagrangian relaxation
memory hierarchy
parallel 0/1 integer linear programming
AI Summary

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.

Journal

Annals of Operations Research cover
Annals of Operations Research
IF:
4.5
Papers:
8.0K
Citations:
2.1W

Organization

No organization information available