ICM 1998, Berlin, Aug. 18–27

Abstracts of Plenary and Invited Lectures

Section:

17. Control Theory and Optimization

1991 MS Classification: 65Y20 Pulleyblank, William R., T. J. Watson Res. Center, IBM, New York, USA Advances in Solving Airline Crew Pairing Optimization Problems

Airline Crew Scheduling Problems provide an important class of very large set packing problems. The problem is to determine a set of pairings, legal sequences of duties for airline crews, which minimize the cost of the associated schedule. Part of the difficulty of this problem arises from the complexity of both the feasibility rules and the cost structure. Part is also due to the very large size of the set P of feasible pairings. Traditionally the problem is formulated as the following integer program:

Minimize ∑_{j∈P} c_{j}x_{j}
subject to x_{j} ∈ {0, 1}for all j ∈ P
∑_{j∈P (d)} x_{j} = 1 for all flights d

where for each scheduled flight d, P (d) is the set of feasible pairings that cover that flight. Successfully solving these problems require specialized integer programming methods, combined with methods for generating feasible pairings which can be combined to yield the required low cost solution. We discuss the general problem as well as the differences between domestic and short haul versions. After surveying previous approaches, we describe how subgradient methods for approximating the solutions of the underlying linear programs yield approximate dual solutions which greatly improve the performance of the column generator and actually enable Dantzig-Wolfe decomposition to become an effective solution procedure. We also present computational experience using these methods on problems arising from several airlines. This is joint work with Ranga Anbil and John Forrest of IBM Research.

ICM 1998 Berlin · Plenary and Invited Lectures