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

Simple item page
dc.contributorVirginia Techen
dc.contributor.authorSubramanian, Shivaramen
dc.contributor.authorSherali, Hanif D.en
dc.contributor.departmentIndustrial and Systems Engineeringen
dc.date.accessed2014-02-05en
dc.date.accessioned2014-03-05T14:00:24Zen
dc.date.available2014-03-05T14:00:24Zen
dc.date.issued2008en
dc.description.abstractWe 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.en
dc.description.sponsorshipNSF 094462, 0245643en
dc.format.mimetypeapplication/pdfen
dc.identifier.citationSubramanian, Shivaram; Sherali, Hanif D. An Effective Deflected Subgradient Optimization Scheme for Implementing Column Generation for Large-Scale Airline Crew Scheduling Problems. INFORMS Journal on Computing 2008 20:4, 565-578. doi: 10.1287/ijoc.1080.0267en
dc.identifier.doihttps://doi.org/10.1287/ijoc.1080.0267en
dc.identifier.issn1091-9856en
dc.identifier.urihttp://hdl.handle.net/10919/25837en
dc.identifier.urlhttp://pubsonline.informs.org/doi/pdf/10.1287/ijoc.1080.0267en
dc.language.isoenen
dc.publisherINFORMSen
dc.rightsIn Copyrighten
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subjectAirline crew planningen
dc.subjectSet-partitioning problemsen
dc.subjectDeflected subgradienten
dc.subjectApproachen
dc.subjectDual noiseen
dc.subjectVariable target valueen
dc.subjectVariable target valueen
dc.subjectVolume algorithmen
dc.subjectPrimal solutionsen
dc.subjectLinear-programsen
dc.subjectConstraintsen
dc.titleAn Effective Deflected Subgradient Optimization Scheme for Implementing Column Generation for Large-Scale Airline Crew Scheduling Problemsen
dc.title.serialInforms Journal on Computingen
dc.typeArticle - Refereeden
dc.type.dcmitypeTexten

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
ijoc%2E1080%2E0267.pdf
Size:
851.01 KB
Format:
Adobe Portable Document Format
Description:
Main article
Download

Collections

Scholarly Works, Industrial and Systems Engineering