期刊
INFORMS JOURNAL ON COMPUTING
卷 20, 期 4, 页码 565-578出版社
INFORMS
DOI: 10.1287/ijoc.1080.0267
关键词
airline crew planning; set-partitioning problems; deflected subgradient approach; dual noise; variable target value method
资金
- National Science Foundation [0094462, 0245643]
- Enterprise Optimization, United Airlines
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 motivation for the development of this method came from the failure of a black-box-type 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 an average speed-up factor of 10 for the column generation scheme over the commercial solver, the average reduction in the optimality gap over the same number of iterations was better by a factor of 26, along with an average 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 column generation scheme.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据