An Effective Deflected Subgradient Optimization Scheme for Implementing Column Generation for Large-Scale Airline Crew Scheduling Problems.

We present a new deflected subgradient scheme for generating good quality dual solutions for linear programming (LP) problems and utilize this within the context of large-scale airline crew planning problems that arise inpractice. The motivationfor the development of this method came from the failure of a black-boxtype approach implemented at United Airlines for solving such problems using column generation in concert with a commercial LP solver, where the software was observed to stall while yet remote from optimality. We identify a phenomenon called dual noise to explain this stalling behavior and present an analysis of the desirable properties of dual solutions in this context. The proposed deflected subgradient approach has been embedded within the crew pairing solver at United Airlines and tested using historical data sets. Our computational experience suggests a strong correlation between the dual noise phenomenon and the quality of the final solution produced, as well as with the accompanying algorithmic performance. Although we observed that our deflected subgradient scheme yielded anaverage speed-up factor of 10 for the columngen erationscheme over the commercial solver, the average reductionin the optimality gap over the same number of iterations was better by a factor of 26, along with anaverage reduction in the dual noise by a factor of 30. The results from the column generation implementation suggest that significant benefits can be obtained by using the deflected subgradient-based scheme instead of a black-box-type or standard solver approach to solve the intermediate linear programs that arise with in the columngen erationscheme. [ABSTRACT FROM AUTHOR]