A new pricing scheme for airline crew scheduling

Alexandra Makri*, Diego Klabjan

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

19 Scopus citations


Solving LP relaxations of airline crew scheduling models is computationally challenging due to the presence of a large number of variables, complex feasibility rules to generate columns, and nonlinear cost. We perform computational experiments with a nonlinear pricing strategy. We develop a column generation scheme that uses several pruning rules to fathom column enumeration. The pruning rules are categorized into approximate and exact, where the approximate rules might prune columns that would yield an improved objective value. The pruning rules use the fact that columns are paths in a network, and we use shortest path algorithms and their extensions to obtain bounds.

Original languageEnglish (US)
Pages (from-to)56-67
Number of pages12
JournalINFORMS Journal on Computing
Issue number1
StatePublished - 2004


  • Programming, linear
  • Scheduling
  • Transportation

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Computer Science Applications
  • Management Science and Operations Research


Dive into the research topics of 'A new pricing scheme for airline crew scheduling'. Together they form a unique fingerprint.

Cite this