Abstract
Column Generation is a very powerful class of combinatorial optimization algorithms that has been used successfully to solve a variety of large scale optimization problems. Its application has helped many companies in various industries increase revenue and reduce costs significantly, particularly in transportation, energy, manufacturing, and telecommunication companies. In this chapter, we will first discuss the motivations for column generation, then we will provide an intuitive but rigorous treatment of the mechanisms of column generation – how it works, why it works. We will then give descriptions on the branch and price algorithm and several examples of column generation’s successful applications in one of the world’s largest airlines. We will discuss monthly airline crew schedule optimization for bidlines, crew pairing optimization, and integrated modeling of fleet and routing in the optimization of aircraft scheduling. Part of the focus is on business requirements and priorities in these areas and how the column generation models are built to effectively meet these challenges. Some airline industry domain-specific details are provided to allow the readers to better appreciate the scheduling problems’ complexities that made the master-subproblem approach in column generation essential. We will also discuss the significant run-time speedups for these large scale scheduling problems due to various practical model enhancements, as well as progress in the large scale optimization space made possible by technologies such as parallel processing, big data, and better chips. At last, we will briefly discuss several example variants of column generation and their applications in various industries. We will also review recent applications of optimization techniques to machine learning as well as the future potentials of large scale optimization in this field. This chapter can be used as a primer on the fundamentals of column generation techniques since it clearly addresses essential theoretical concepts that are sometimes elusive to researchers and graduate students who are new to this area. The chapter should also be helpful to practitioners who would like to gain insights into how to build effective column generation models to solve real world large scale optimization problems.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Banko, M., Brill, E.: Scaling to very very large corpora for natural language disambiguation. In: Proceedings of the 39th Annual Meeting on Association for Computational Linguistics, pp. 26–33 (2001)
Barnhart, C., Boland, N., Clarke, L., Johnson, E., Nemhauser, G., Shenoi, R.: Flight string models for aircraft fleeting and routing. Transp. Sci. 32, 208–220 (1998)
Bertsimas, D., Dunn, J.: Optimal classification trees. Mach. Learn. 106, 1039–1082 (2017)
Breiman, L., Friedman, J., Olshen, R., Stone, C.: Classification and regression trees. Wadsworth Int. 37(15), 237–251 (1984)
Demassey, S., Pesant, G., Rousseau, L.M.: Constraint programming based column generation for employee timetabling. In: Second International Conference, CPAIOR 2005, Prague, Czech Republic. Springer Berlin/Heidelberg, 3524/2005, pp. 140–154, Lecture Notes in Computer Science (2005)
Gilmore, P.C., Gomory, R.E.: A linear programming approach to the cutting stock problem. Oper. Res. 9, 848–859 (1961)
Gilmore, P.C., Gomory, R.E.: A linear programming approach to the cutting stock problem, Part II. Oper. Res. 11, 863–888 (1963)
Gondzio, J., Sarkissian, R.: Column generation with a primal-dual method. Technical report 96.6, Logilab (1996)
Gondzio, J., Gonz’alez-Brevis, P., Munari, P.: New developments in the primal-dual column generation technique. Eur. J. Oper. Res. 224(1), 41–51 (2013)
Gondzio, J., Gonz’alez-Brevis, P., Munari, P.: Large-scale optimization with the primal-dual column generation method. Math. Program. Comput. 8(1), 47–82 (2016)
Kantorovich, L.V.: Mathematical methods of organizing and planning production. Manag. Sci. 6, 366–422 (1960)
Kohl, N., Karisch, S.: Integrating operations research and constraint programming techniques in crew scheduling. In: Proceedings of the 40th Annual AGIFORS Symposium, 20–25 August (2000)
Kohl, N., Karisch, S.: Airline crew rostering: problem types, modeling, and optimization. Ann. Oper. Res. 127(1), 223–257 (2004)
Punyakanok, V., Roth, D., Yih, W., Zimak, D.: Semantic role labeling via integer linear programming inference. In: Proceedings of COLING-2004 (2004)
Roth, D., Yih, D.: Integer linear programming inference for conditional random fields. In: Proceedings of 22nd International Conference on Machine Learning (2005)
Sellmann, M., Zervoudakis, K., Stamatopoulos, P., Fahle, T.: Crew assignment via constraint programming: integrating column generation and heuristic tree search. Ann. Oper. Res. 115(1–4), 207–225 (2002)
Vance P.H., et al.: A heuristic branch and price approach for the airline crew scheduling problem. Technical report (1997)
Wedelin, D.: An algorithm for large scale 0–1 integer programming with application to airline crew scheduling. Ann. Oper. Res. 57(1), 283–301 (1995)
Zeng, B., Zhao, L.: Solving two-stage robust optimization problems using a column-and-constraint generation method. Oper. Res. Lett. 41(5), 457–461 (2013)
Zhao, L., Zeng, B.: Robust unit commitment problem with demand response and wind energy. Technical report, available in optimization-online, University of South Florida (2010)
Acknowledgments
We sincerely thank the editors for their valuable guidance and support. Also we are most grateful to the anonymous reviewers for their very insightful feedback and comments. In addition, we would like to express our deep appreciation to Sharon Xu of MIT for proofreading the manuscript and for her many helpful revision suggestions.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this chapter
Cite this chapter
Xu, Y. (2019). Solving Large Scale Optimization Problems in the Transportation Industry and Beyond Through Column Generation. In: Fathi, M., Khakifirooz, M., Pardalos, P.M. (eds) Optimization in Large Scale Problems. Springer Optimization and Its Applications, vol 152. Springer, Cham. https://doi.org/10.1007/978-3-030-28565-4_23
Download citation
DOI: https://doi.org/10.1007/978-3-030-28565-4_23
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-28564-7
Online ISBN: 978-3-030-28565-4
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)