The DOI matches its Crossref record; 73 of the 73 references it cites were found in a registry or an index.
Selected Topics in Column Generation
Open accessAbstract
Dantzig-Wolfe decomposition and column generation, devised for linear programs, is a success story in large-scale integer programming. We outline and relate the approaches, and survey mainly recent contributions, not yet found in textbooks. We emphasize the growing understanding of the dual point of view, which has brought considerable progress to the column generation theory and practice. It stimulated careful initializations, sophisticated solution techniques for the restricted master problem and subproblem, as well as better overall performance. Thus, the dual perspective is an ever recurring concept in our “selected topics.”
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
An Algorithm for Least-Squares Estimation of Nonlinear Parameters
Marquardt, D. W. (1963) · Journal of the Society for Industrial and Applied Mathematics · doi:10.1137/0111030 · Cited by 30,728
Theory of Linear and Integer Programming
Letchford, A. N., & Schrijver, A. (2000) · The Journal of the Operational Research Society · doi:10.2307/253980 · Cited by 5,515
Integer and Combinatorial Optimization
Williams, H. P., Nemhauser, G. L., & Wolsey, L. A. (1990) · Journal of the Operational Research Society · doi:10.2307/2583737 · Cited by 5,485
(2002) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9780898718515 · Cited by 4,008
Partitioning procedures for solving mixed-variables programming problems
Benders, J. F. (1962) · Numerische Mathematik · doi:10.1007/bf01386316 · Cited by 3,855
Geometric Algorithms and Combinatorial Optimization
Grötschel, M., Lovász, L., & Schrijver, A. (1988) · Algorithms and Combinatorics · doi:10.1007/978-3-642-97881-4 · Cited by 3,431
Nemhauser, G. L., & Wolsey, L. A. (1972) · Cited by 3,365
Integer and Combinatorial Optimization
Nemhauser, G., & Wolsey, L. (1988) · Wiley eBooks · doi:10.1002/9781118627372 · Cited by 3,176
Theory of Linear and Integer Programming
Smith, D. K. (1987) · Journal of the Operational Research Society · doi:10.1057/jors.1987.94 · Cited by 2,708
Decomposition Principle for Linear Programs
Dantzig, G. B., & Wolfe, P. (1960) · Operations Research · doi:10.1287/opre.8.1.101 · Cited by 2,315
Branch-and-price: column generation for solving huge integer programs
Barnhart, C., Johnson, E. L., Nemhauser, G. L., Savelsbergh, M. W. P., & Vance, P. H. (1998) · Operations Research · doi:10.1287/opre.46.3.316 · Cited by 2,219
A Linear Programming Approach to the Cutting-Stock Problem
Gilmore, P. C., & Gomory, R. E. (1961) · Operations Research · doi:10.1287/opre.9.6.849 · Cited by 2,024
Optimization Theory of Large Systems
Lasdon, L. S., & Tabak, D. (1971) · IEEE Transactions on Systems, Man, and Cybernetics · doi:10.1109/tsmc.1971.4308301 · Cited by 1,677
The Cutting-Plane Method for Solving Convex Programs
Kelley, Jr. (1960) · Journal of the Society for Industrial and Applied Mathematics · doi:10.1137/0108053 · Cited by 1,549
A New Optimization Algorithm for the Vehicle Routing Problem with Time Windows
Desrochers, M., Desrosiers, J., & Solomon, M. (1992) · Operations Research · doi:10.1287/opre.40.2.342 · Cited by 1,197
Self-citationA Linear Programming Approach to the Cutting Stock Problem—Part II
Gilmore, P. C., & Gomory, R. E. (1963) · Operations Research · doi:10.1287/opre.11.6.863 · Cited by 1,119
Lagrangean relaxation for integer programming
Geoffrion, A. M. (1974) · Mathematical Programming Studies · doi:10.1007/bfb0120690 · Cited by 1,111
Mathematical Methods of Organizing and Planning Production
Kantorovich, L. V. (1960) · Management Science · doi:10.1287/mnsc.6.4.366 · Cited by 1,082
Lagrangian Relaxation for Integer Programming
Geoffrion, A. M. (2010) · 50 Years of Integer Programming 1958-2008 · doi:10.1007/978-3-540-68279-0_9 · Cited by 974
Partitioning procedures for solving mixed-variables programming problems
Benders, J. F. (2005) · Computational Management Science · doi:10.1007/s10287-004-0020-y · Cited by 837
Time Constrained Routing and Scheduling
Desrosiers, J., Solomon, M. M., Soumis, F., & Dumas, Y. (1992) · PolyPublie (École Polytechnique de Montréal) · doi:10.1016/s0927-0507%2805%2980106-9 · Cited by 709
Self-citationA Branch-and-Price Algorithm for the Generalized Assignment Problem
Savelsbergh, M. (1997) · Operations Research · doi:10.1287/opre.45.6.831 · Cited by 437
2-Path Cuts for the Vehicle Routing Problem with Time Windows
Kohl, N., Desrosiers, J., Madsen, O. B. G., Solomon, M. M., & Soumis, F. (1999) · Transportation Science · doi:10.1287/trsc.33.1.101 · Cited by 411
Self-citationA Column Generation Approach for Graph Coloring
Mehrotra, A., & Trick, M. A. (1996) · INFORMS Journal on Computing · doi:10.1287/ijoc.8.4.344 · Cited by 410
Annotated Bibliographies in Combinatorial Optimization.
Wilson, J. M., Dell’Amico, M., Maffioli, F., & Martello, S. (1998) · Journal of the Operational Research Society · doi:10.2307/3010676 · Cited by 394
Solving Real-World Linear Programs: A Decade and More of Progress
Bixby, R. E. (2002) · Operations Research · doi:10.1287/opre.50.1.3.17780 · Cited by 386
Chapter 2 Time constrained routing and scheduling
Desrosiers, J., Dumas, Y., Solomon, M. M., & Soumis, F. (1995) · Handbooks in Operations Research and Management Science · doi:10.1016/s0927-0507(05)80106-9 · Cited by 374
Self-citationExact solution of bin‐packing problems using column generation and branch‐and‐bound
de Carvalho, J. V. (1999) · Annals of Operations Research · doi:10.1023/a:1018952112615 · Cited by 373
Routing with time windows by column generation
Desrosiers, J., Soumis, F., & Desrochers, M. (1984) · Networks · doi:10.1002/net.3230140406 · Cited by 366
Self-citationFlight String Models for Aircraft Fleeting and Routing
Barnhart, C., Boland, N. L., Clarke, L. W., Johnson, E. L., Nemhauser, G. L., & Shenoi, R. G. (1998) · Transportation Science · doi:10.1287/trsc.32.3.208 · Cited by 360
du Merle, O., Villeneuve, D. L., Desrosiers, J., & Hansen, P. (1999) · Discrete Mathematics · doi:10.1016/s0012-365x(98)00213-1 · Cited by 351
Self-citationDrive: Dynamic Routing of Independent Vehicles
Savelsbergh, M., & Sol, M. (1998) · Operations Research · doi:10.1287/opre.46.4.474 · Cited by 334
A Column Generation Approach to the Urban Transit Crew Scheduling Problem
Desrochers, M., & Soumis, F. (1989) · Transportation Science · doi:10.1287/trsc.23.1.1 · Cited by 332
A Suggested Computation for Maximal Multi-Commodity Network Flows
Ford, L. R., & Fulkerson, D. R. (2004) · Management Science · doi:10.1287/mnsc.1040.0269 · Cited by 326
Using Branch-and-Price-and-Cut to Solve Origin-Destination Integer Multicommodity Flow Problems
Barnhart, C., Hane, C. A., & Vance, P. H. (2000) · Operations Research · doi:10.1287/opre.48.2.318.12378 · Cited by 325
A Suggested Computation for Maximal Multi-Commodity Network Flows
Ford, L. R., & Fulkerson, D. R. (1958) · Management Science · doi:10.1287/mnsc.5.1.97 · Cited by 325
Vanderbeck, F. (2000) · Operations Research · doi:10.1287/opre.48.1.111.12453 · Cited by 291
An exact algorithm for IP column generation
Vanderbeck, F., & Wolsey, L. A. (1996) · Operations Research Letters · doi:10.1016/0167-6377(96)00033-8 · Cited by 244
A Column Generation Approach for Large-Scale Aircrew Rostering Problems
Gamache, M., Soumis, F., Marquis, G., & Desrosiers, J. (1999) · Operations Research · doi:10.1287/opre.47.2.247 · Cited by 239
Self-citationA Unified Framework for Deterministic Time Constrained Vehicle Routing and Crew Scheduling Problems
Desaulniers, G., Desrosiers, J., loachim, I., Solomon, M. M., Soumis, F., & Villeneuve, D. (1998) · Fleet Management and Logistics · doi:10.1007/978-1-4615-5755-5_3 · Cited by 238
Self-citationDaily Aircraft Routing and Scheduling
Desaulniers, G., Desrosiers, J., Dumas, Y., Solomon, M. M., & Soumis, F. (1997) · Management Science · doi:10.1287/mnsc.43.6.841 · Cited by 227
Self-citationComputational study of a column generation algorithm for bin packing and cutting stock problems
Vanderbeck, F. (1999) · Mathematical Programming · doi:10.1007/s101070050105 · Cited by 226
Solving binary cutting stock problems by column generation and branch-and-bound
Vance, P. H., Barnhart, C., Johnson, E. L., & Nemhauser, G. L. (1994) · Computational Optimization and Applications · doi:10.1007/bf01300970 · Cited by 226
Johnson, E. L., Mehrotra, A., & Nemhauser, G. L. (1993) · Mathematical Programming · doi:10.1007/bf01585164 · Cited by 225
2-Path Cuts for the Vehicle Routing Problem with Time Windows
Desrosiers, J., Solomon, M. M., Soumis, F., Kohl, N., & Madsen, O. B. G. (1997) · Les Cahiers du GERAD · Cited by 225
Self-citationA Column Generation Approach to the Multiple-Depot Vehicle Scheduling Problem
Ribeiro, C. C., & Soumis, F. (1994) · Operations Research · doi:10.1287/opre.42.1.41 · Cited by 216
The Shortest-Path Problem with Resource Constraints and k-Cycle Elimination for k ≥ 3
Irnich, S., & Villeneuve, D. (2006) · INFORMS Journal on Computing · doi:10.1287/ijoc.1040.0117 · Cited by 215
Kohl, N., & Madsen, O. B. G. (1997) · Operations Research · doi:10.1287/opre.45.3.395 · Cited by 215
Branch-and-Price Algorithms for the One-Dimensional Cutting Stock Problem
Vance, P. H. (1998) · Computational Optimization and Applications · doi:10.1023/a:1018346107246 · Cited by 188
Computer Scheduling of Public Transport: Urban Passenger Vehicle and Crew Scheduling
Feder, P. I. (1982) · Technometrics · doi:10.1080/00401706.1982.10487724 · Cited by 186
Ioachim, I., G�linas, S., Soumis, F., & Desrosiers, J. (1998) · Networks · doi:10.1002/(sici)1097-0037(199805)31:3<193::aid-net6>3.0.co;2-a · Cited by 181
Self-citationAn algorithm for large scale 0–1 integer programming with application to airline crew scheduling
Wedelin, D. (1995) · Annals of Operations Research · doi:10.1007/bf02099703 · Cited by 165
Implementing Mixed Integer Column Generation
Vanderbeck, F. (2006) · Springer eBooks · doi:10.1007/0-387-25486-2_12 · Cited by 164
Very Large-Scale Linear Programming: A Case Study in Combining Interior Point and Simplex Methods
Bixby, R. E., Gregory, J. W., Lustig, I. J., Marsten, R. E., & Shanno, D. F. (1992) · Operations Research · doi:10.1287/opre.40.5.885 · Cited by 164
Vehicle Scheduling in Public Transit and Lagrangean Pricing
Löbel, A. (1998) · Management Science · doi:10.1287/mnsc.44.12.1637 · Cited by 135
Resource Constrained Shortest Paths
Mehlhorn, K., & Ziegelmann, M. (2000) · Lecture Notes in Computer Science · doi:10.1007/3-540-45253-2_30 · Cited by 124
A technical review of column generation in integer programming
Wilhelm, W. E. (2001) · Optimization and Engineering · doi:10.1023/a:1013141227104 · Cited by 108 · cited 1×
“Previous general reviews include those by Desrosiers et al. (1995), Soumis (1997), and Wilhelm (2001).”
BackgroundA Note on Bounding a Class of Linear Programming Problems, Including Cutting Stock Problems
Farley, A. (1990) · Operations Research · doi:10.1287/opre.38.5.922 · Cited by 96
The Preferential Bidding System at Air Canada
Gamache, M., Soumis, F., Villeneuve, D. L., Desrosiers, J., & Gélinas, É. (1998) · Transportation Science · doi:10.1287/trsc.32.3.246 · Cited by 85
Self-citationSolving large scale crew scheduling problems
Chu, H. D., Gelman, E., & Johnson, E. L. (1997) · European Journal of Operational Research · doi:10.1016/s0377-2217(96)00196-8 · Cited by 77
Ribeiro, C. C., Minoux, M., & Penna, M. C. (1989) · European Journal of Operational Research · doi:10.1016/0377-2217(89)90389-5 · Cited by 75
The Column Generation Principle And The Airline Crew Scheduling Problem
Crainic, T. G., & Rousseau, J. M. (1987) · INFOR Information Systems and Operational Research · doi:10.1080/03155986.1987.11732034 · Cited by 75
Modeling and Strong Linear Programs for Mixed Integer Programming
Johnson, E. L. (1989) · Springer eBooks · doi:10.1007/978-3-642-83724-1_1 · Cited by 61
On Compact Formulations for Integer Programs Solved by Column Generation
Villeneuve, D. L., Desrosiers, J., Lübbecke, M. E., & Soumis, F. (2005) · Annals of Operations Research · doi:10.1007/s10479-005-3455-9 · Cited by 60
Self-citationDuty Scheduling in Public Transit
Grötschel, M., Borndörfer, R., & Löbel, A. (2003) · Springer eBooks · doi:10.1007/978-3-642-55753-8_50 · Cited by 51
Column generation techniques for pickup and delivery problems
Sol, M. M. (1994) · TU/e Research Portal · doi:10.6100/ir423957 · Cited by 50
Integer multicommodity flow problems
Barnhart, C., Hane, C. A., & Vance, P. H. (1996) · Lecture notes in computer science · doi:10.1007/3-540-61310-2_5 · Cited by 43
Minoux, M. (1987) · RAIRO - Operations Research · doi:10.1051/ro/1987210201051 · Cited by 36
A Note on Branch-and-Price Algorithms for the One-Dimensional Cutting Stock Problems
de Carvalho, J. V. (2002) · Computational Optimization and Applications · doi:10.1023/a:1013733421344 · Cited by 26
Integer Multicommodity Flow Problems
Barnhart, C., Hane, C. A., & Vance, P. H. (1997) · Lecture notes in economics and mathematical systems · doi:10.1007/978-3-642-59179-2_2 · Cited by 24
Mixed-integer column generation algorithms and the probabilistic maximum satisfiability problem
Hansen, P., Jaumard, B., & de Aragão, M. P. (1998) · European Journal of Operational Research · doi:10.1016/s0377-2217(97)00059-3 · Cited by 21
A combinatorial column generation algorithm for the maximum stable set problem
Bourjolly, J.-M., Gilbert Laporte, A., & Mercure, H. (1997) · Operations Research Letters · doi:10.1016/s0167-6377(96)00038-7 · Cited by 17
Circuit Partitioning Via Set Partitioning and Column Generation
Eben‐Chaime, M., Tovey, C. A., & Ammons, J. C. (1996) · Operations Research · doi:10.1287/opre.44.1.65 · Cited by 12
Research works printed but not linked: 54
- Adler I., 1973, Decomposition of Large Scale Problems, 181
- 10.1002/net.3230190702 · doi:10.1002/net.3230190702
- Anbil R., 1998, Proc. Internat. Congress of Mathematicians Berlin, 677
- 10.1007/s101070050002 · doi:10.1007/s101070050002
- 10.1016/S0166-218X(01)00252-9 · doi:10.1016/s0166-218x(01)00252-9
- 10.1007/BF02680552 · DOI
- 10.1287/opre.44.6.852 · DOI
- Ben Amor H. Stabilisation de l’algorithme de génération de colonnes. (2002) . Ph.D. thesis, École Polytechnique de Montréal, Montréal, Québec, Canada
- Borndörfer R., 2003, Mathematics—Key Technology for the Future, 653
- 10.1287/opre.47.5.730 · DOI
- 10.1023/A:1019225027893 · DOI
- Chvátal V., 1983, Linear Programming
- Crainic T. G., 1987, Infor, 25, 136
- 10.1016/0377-2217(94)90122-8 · doi:10.1016/0377-2217(94)90122-8
- Desaulniers G., 2001, Essays and Surveys in Metaheuristics, 309
- 10.1287/opre.1050.0222 · DOI
- 10.1007/s10107-003-0469-4 · DOI
- 10.1023/A:1014998931654 · DOI
- 10.1007/BF01581089 · doi:10.1007/bf01581089
- 10.1080/1055678021000060829a · doi:10.1080/1055678021000060829a
- 10.1016/0377-2217(93)90129-B · doi:10.1016/0377-2217(93)90129-b
- 10.1007/BF01593804 · doi:10.1007/bf01593804
- 10.1007/BF01580108 · doi:10.1007/bf01580108
- Hiriart-Urruty J.-B., 1993, Convex Analysis and Minimization Algorithms, Part 2: Advanced Theory and Bundle Methods, 306
- 10.1016/0167-6377(84)90048-8 · doi:10.1016/0167-6377(84)90048-8
- 10.1016/0166-218X(88)90077-7 · doi:10.1016/0166-218x(88)90077-7
- 10.1080/02331939508844100 · doi:10.1080/02331939508844100
- 10.1007/s11766-997-0022-y · doi:10.1007/s11766-997-0022-y
- 10.1016/S0377-2217(98)00343-9 · DOI
- Irnich S., 2003, INFORMS J. Comput.
- 10.1016/0024-3795(91)90270-7 · doi:10.1016/0024-3795(91)90270-7
- 10.1016/S0305-0548(98)00101-4 · doi:10.1016/s0305-0548(98)00101-4
- 10.1007/3-540-48777-8_24 · doi:10.1007/3-540-48777-8_24
- 10.1007/3-540-45749-6_56 · doi:10.1007/3-540-45749-6_56
- 10.1287/trsc.37.2.183.15251 · DOI
- 10.1093/imamat/16.3.321 · doi:10.1093/imamat/16.3.321
- Mahey P., 1986, Proc. X. Sympos. Oper. Res., Part I: Sections 1–5. Methods in Operations Research, 697
- 10.1287/mnsc.46.5.693.12042 · doi:10.1287/mnsc.46.5.693.12042
- 10.1007/BFb0120702 · doi:10.1007/bfb0120702
- 10.1287/opre.23.3.389 · doi:10.1287/opre.23.3.389
- Minoux M., 1986, Mathematical Programming
- 10.1016/0024-3795(84)90186-1 · doi:10.1016/0024-3795(84)90186-1
- Nazareth J. L., 1987, Computer Solution of Linear Programs
- 10.1287/mnsc.42.9.1277 · doi:10.1287/mnsc.42.9.1277
- Poggi de Aragão M., 2003, Proc. Conf. Math. Program in Rio: A Conf. in Honour of Nelson Maculan, 56
- 10.1016/0377-2217(94)00150-B · doi:10.1016/0377-2217(94)00150-b
- Senne E. L. F., 2001, EURO 2001—The European Operational Res. Conference
- 10.1007/BF01580252 · doi:10.1007/bf01580252
- 10.1016/S0377-2217(02)00124-8 · DOI
- 10.1007/BF02591718 · doi:10.1007/bf02591718
- Vanderbeck F. Decomposition and column generation for integer programs. (1994) . Ph.D. thesis, Université Catholique de Louvain, Louvain-la-Neuve, Belgium
- Villeneuve D. Logiciel de génération de colonnes. (1999) . Ph.D. thesis, École Polytechnique de Montréal, Montréal, Québec, Canada
- 10.1287/opre.17.2.368 · doi:10.1287/opre.17.2.368
- 10.1111/j.1475-3995.1997.tb00071.x · doi:10.1111/j.1475-3995.1997.tb00071.x
Cited by
Feillet, D., Dejax, P., Gendreau, M., & Gueguen, C. (2004) · Networks · doi:10.1002/net.20033 · Cited by 693
Uncertain convex programs: randomized solutions and confidence levels
Calafiore, G., & Campi, M. C. (2005) · Mathematical Programming · doi:10.1007/s10107-003-0499-y · Cited by 659
Branch-and-bound algorithms: A survey of recent advances in searching, branching, and pruning
Morrison, D. R., Jacobson, S. H., Sauppe, J. J., & Sewell, E. C. (2016) · Discrete Optimization · doi:10.1016/j.disopt.2016.01.005 · Cited by 563
Exact Algorithms for Electric Vehicle-Routing Problems with Time Windows
Desaulniers, G., Errico, F., Irnich, S., & Schneider, M. (2016) · Operations Research · doi:10.1287/opre.2016.1535 · Cited by 497
Subset-Row Inequalities Applied to the Vehicle-Routing Problem with Time Windows
Jepsen, M., Petersen, B., Spoorendonk, S., & Pisinger, D. (2008) · Operations Research · doi:10.1287/opre.1070.0449 · Cited by 410
Metadata
- Authors
- Lübbecke, M. E., & Desrosiers, J.
- Venue
- Operations Research
- Published
- 2005-12
- Volume
- 53
- Issue
- 6
- Pages
- 1007-1023
- ISSN
- 0030-364X (ISSN-L)
- 1526-5463
- OpenAlex
- W1970355999
- Cited by
- 1,102
- References
- 73
- FWCI
- 34.79
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.