Delayed Column Generation: Solving Large-Scale Optimization Models From the Airline Industry

Over the past several decades, the airline industry has widely used sophisticated large-scale optimization models and algorithms to improve operational efficiency, increase revenue, and improve profitability. This chapter discusses one such large-scale optimization technique called Delayed Column Generation. The approach is commonly used to solve instances of several challenging optimization models involving strategic business and operational processes. For example, the classical aircraft rotation set partitioning optimization model is routinely solved using delayed column generation. This chapter delves into the details of the delayed column generation and branch-and-price computational procedures. To illustrate their applicability in real-world airline models, we describe a simple application to the aircraft rotation model. Additionally, we provide a few references to articles describing other applications in the airline industry.