×

Column-generation in integer linear programming. (English) Zbl 1036.90076

This article presents an exact method for solving integer and binary linear programming problems based on the branch-and-price technique.
The article begins with an overview of branch-and-price column generation techniques as applied to integer linear programs (LP), which is then followed by an overview of applications, e.g., the vehicle routing problem with and without time windows, the crew scheduling problem and the one dimensional cutting stock problem.
In the second section, the authors present the column generation branch-and-price technique for a general linear program with bounded variables. This is followed by a series of inequalities that are used to prevent generating the same columns twice. The solution technique presented by the authors then follows in section 4.
The article concludes with section 5 which contains a series of computational results using the integer programming formulation of a network design problem.

MSC:

90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90C10 Integer programming
90C05 Linear programming
PDFBibTeX XMLCite
Full Text: DOI Numdam Numdam EuDML

References:

[1] R. Anbil , J. Forrest and W. Pulleyblank , Column generation and the airline crew pairing problem . DOC. Math. J. DMV ( 1998 ) 677 - 686 . MR 1648197 | Zbl 0904.90082 · Zbl 0904.90082
[2] C. Barnhart , C. Hanne and P.H. Vance , Using branch-and-price and cut to solve origin destination integer multicommodity flow problems . Oper. Res. 48 ( 2000 ) 318 - 326 .
[3] C. Barnhart , E.L. Johnson , G.L. Nemhauser , M.W.P. Savelsbergh and P.H. Vance , Branch-and-price: Column generation for solving huge integer programs . Oper. Res. 46 ( 1998 ) 316 - 329 . MR 1663050 | Zbl 0979.90092 · Zbl 0979.90092 · doi:10.1287/opre.46.3.316
[4] R. Borndorfer , M. Grotschel and A. Lobel , Scheduling duties by adptive column generation . ZIB-Report 01 - 02 ( 2001 ).
[5] J. Bourjolly , G. Laporte and H. Mercure , A combinatorial column generation algorithm for the maximun stable set problem . Oper. Res. Lett. ( 1997 ). MR 1428385 | Zbl 0892.90176 · Zbl 0892.90176 · doi:10.1016/S0167-6377(96)00038-7
[6] J.A.M. Brito , Um modelo de otimização para dimensionamento de uma rede de telecomunicações , Tese de mestrado, COPPE. Universidade Federal do Rio de Janeiro, Rio de Janeiro, Brasil ( 1999 ).
[7] J. Bramel and D. Simchi-Levi , On the effectiveness of set covering formulations for the vehicle routing problem with time windows . Oper. Res. 45 ( 1997 ) 295 - 301 . Zbl 0890.90054 · Zbl 0890.90054 · doi:10.1287/opre.45.2.295
[8] S. Butt and D.M. Ryan , An optimal solution procedure for the multiple tour maximum collec tion problem using column generation . Comp. Oper. Res. 26 ( 1999 ) 427 - 441 . MR 1678298 | Zbl 0951.90007 · Zbl 0951.90007 · doi:10.1016/S0305-0548(98)00071-9
[9] Z. Chen and W. Powell , A column generation based descomposition algorithm for a parallel machine scheduling problem . EJOR 116 ( 1999 ) 220 - 232 . Zbl 1009.90040 · Zbl 1009.90040 · doi:10.1016/S0377-2217(98)00136-2
[10] V. Chvátal , Linear programming . W.H. Freeman and Company, New York, San Francisco ( 1983 ). MR 717219 | Zbl 0537.90067 · Zbl 0537.90067
[11] Y. Crama and J. Van de Klundert , Approximation algorithms for integer covering problems via greedy column generation . RAIRO: Oper. Res. 28 ( 1994 ) 283 - 302 . Numdam | MR 1290532 | Zbl 0830.90107 · Zbl 0830.90107
[12] R. Dakin , A tree search algorithm for mixed integer programming problems . Comput. J. 8 ( 1965 ) 250 - 255 . MR 187937 | Zbl 0154.42004 · Zbl 0154.42004 · doi:10.1093/comjnl/8.3.250
[13] G.B. Dantzig , Upper bounds, secondary constraints and block triangulary in linear programming . Econometrica 23 ( 1995 ) 174 - 183 . MR 70931 | Zbl 0064.39501 · Zbl 0064.39501 · doi:10.2307/1907876
[14] G.B. Dantzig , Linear programming and extensions . Princeton University Press, New Jersey, USA ( 1963 ). MR 201189 | Zbl 0108.33103 · Zbl 0108.33103
[15] G.B. Dantzig and P. Wolfe , Decomposition principle for linear programming . Oper. Res. 8 ( 1960 ) 101 - 111 . Zbl 0093.32806 · Zbl 0093.32806 · doi:10.1287/opre.8.1.101
[16] J.M.V. de Carvalho , Exact solution of cutting stock problems using column generation and branch-and-bound . Int. Trans. Oper. Res. 5 ( 1998 ) 35 - 43 . Zbl 0911.90281 · Zbl 0911.90281 · doi:10.1111/j.1475-3995.1998.tb00100.x
[17] J. Delorme , Contributions à la résolution du problème de recouvrement : méthode de troncature , Docteur-ingenieur dissertation. Université Paris VI, Paris, France ( 1974 ).
[18] G. Desaulniers , J. Desrosiers and M. Solomon , Accelerating strategies in Column Generation methods for vehicle routing and crew scheduling . Cahiers du Gerad G- 99 - 36 ( 1999 ). · Zbl 1017.90045
[19] G. Desaulniers , J. Desrosiers , Y. Dumas and M. Solomon , Daily Aircraft routing and Scheduling . Cahiers du Gerad G- 94 - 21 ( 1994 ). · Zbl 0890.90057
[20] G. Desaulniers , J. Desrosiers and M. Solomon , Accelerating strategies in Column Generation Methods for Vehicle Routing and crew scheduling problems . Cahiers du Gerad G- 99 - 36 ( 1994 ). · Zbl 1017.90045
[21] M. Desrochers , J. Desrosiers and M. Solomon , A new optimization algorithm for the vehicle routing problem with time windows . Oper. Res. 40 ( 1992 ) 342 - 353 . MR 1162951 | Zbl 0749.90025 · Zbl 0749.90025 · doi:10.1287/opre.40.2.342
[22] J. Desrosiers , Y. Dumas , M.N. Solomon and F. Soumis , Time constrained routing and scheduling , edited by M.O. Ball, T.L. Magnanti, C.L. Monma and G.L. Nemhauser, Network Routing. INFORMS - North Holland, Handbooks Oper. Res. Management Sci. 8 ( 1995 ) 35 - 139 . MR 1419994 | Zbl 0861.90052 · Zbl 0861.90052
[23] J. Desrochers and F. Soumis , A column-generation approach to the urban transit crew scheduling problem . Transportation Sci. 23 ( 1989 ) 1 - 13 . Zbl 0668.90043 · Zbl 0668.90043 · doi:10.1287/trsc.23.1.1
[24] J. Desrosiers , F. Soumis and M. Desrochers , Routing with time-windows by column generation . Networks 14 ( 1984 ) 545 - 565 . Zbl 0571.90088 · Zbl 0571.90088 · doi:10.1002/net.3230140406
[25] M. EbenChaime , C. Tovey and J.C. Ammons , Circuit partitioning via set partitioning and column generation . Oper. Res. 44 ( 1996 ) 65 - 76 . Zbl 0847.90095 · Zbl 0847.90095 · doi:10.1287/opre.44.1.65
[26] M. Gamache , F. Soumis , G. Marquis and J. Desrosiers , A column generation approach for large-scale aircrew rostering problems . Oper. Res. 48 ( 1992 ) 247 - 263 . Zbl 1041.90513 · Zbl 1041.90513 · doi:10.1287/opre.47.2.247
[27] P.C. Gilmore and R.E. Gomory , A linear programming approach to the cutting stock problem . Oper. Res. 9 ( 1961 ) 849 - 859 . MR 137589 | Zbl 0096.35501 · Zbl 0096.35501 · doi:10.1287/opre.9.6.849
[28] P.C. Gilmore and R.E. Gomory , A linear programming approach to the cutting stock problem - Part II . Oper. Res. 11 ( 1963 ) 863 - 888 . Zbl 0124.36307 · Zbl 0124.36307 · doi:10.1287/opre.11.6.863
[29] P. Hansen , B. Jaumard and M.V. Poggi de Aragão , Un algorithme primal de programmation linéaire généralisée pour les programmes mixtes . C. R. Acad. Sci. Paris Sér. I Math. 313 ( 1991 ) 557 - 560 . MR 1133483 | Zbl 0737.90045 · Zbl 0737.90045
[30] B. Jaumard , P. Labit and C. Ribeiro , A Column Generation Aproach to Cell Formation Problems in Cellular Manufacturing . Cahiers du Gerad G- 99 - 20 ( 1999 ).
[31] B. Jaumard , C. Meyer and T. Vovor , How to combine a column and row generation method with a column or row elimination procedures - Application to a channel Assiggnment problem . Cahiers du Gerad G- 99 - 18 ( 1999 ).
[32] B. Jaumard , C. Meyer and T. Vovor , Column/Row Generation and Elimination Methods . Cahiers du Gerad G- 99 - 34 ( 1999 ).
[33] E. Johnson , A. Mehrotal and G.L. Nemhauser , Min-cut clustering . Math. Programming 62 ( 1993 ) 133 - 152 . MR 1247611 | Zbl 0807.90117 · Zbl 0807.90117 · doi:10.1007/BF01585164
[34] L. Kroon and M. Fischetti , Crew Scheduling for Netherlands Railways “Destination Customer” (2001). Zbl 0989.90516 · Zbl 0989.90516
[35] L.S. Lasdon , Optimization Theory for Large Systems . Macmillan, New York, USA ( 1970 ). MR 337317 | Zbl 0224.90038 · Zbl 0224.90038
[36] A. Lobel , Vehicle scheduling in public transit and Lagrangian pricing . Management Sci. 44 ( 1998 ) 1637 - 1649 . Zbl 0989.90024 · Zbl 0989.90024 · doi:10.1287/mnsc.44.12.1637
[37] O. Marcotte , The cutting stock problem and integer rounding . Math. Programming 13 ( 1985 ) 82 - 92 . MR 809751 | Zbl 0584.90063 · Zbl 0584.90063 · doi:10.1007/BF01582013
[38] N. Maculan , M. Fampa and P. Michelon , Programação linear e inteira . Notes - COPPE/Universidade Federal do Rio de Janeiro ( 1999 ).
[39] N. Maculan , P. Michelon and G. Plateau , Column generation in linear programming with bounding variable constraints and its applications in integer programming . Pesquisa Operacional 12 ( 1992 ) 45 - 57 .
[40] N. Maculan , M.M. Passini , J.A.M. Brito and A. Lisser , Column generation method for network design , Transportation and Network Analysis Current Trends, edited by M. Gendreau and P. Marcotte. Kluwer Academic Publishers ( 2002 ) 165 - 179 . MR 1909891 | Zbl 1048.90046 · Zbl 1048.90046
[41] A. Mehrotra and M. Trick , A column generation approach for graph coloring . INFORMS J. Comput. 8 ( 1996 ) 344 - 353 . Zbl 0884.90144 · Zbl 0884.90144 · doi:10.1287/ijoc.8.4.344
[42] M. Minoux , Optimal traffic assignment in a SS/TDMA frame: A new approach by set covering and column generation . RAIRO: Oper. Res. 20 ( 1986 ) 273 - 286 . Numdam | Zbl 0608.90076 · Zbl 0608.90076
[43] M. Minoux , A class of combinatorial problems with polynomially solvable large scale set covering/partioning relaxations . RAIRO: Oper. Res. 21 ( 1987 ) 105 - 136 . Numdam | MR 897292 | Zbl 0644.90061 · Zbl 0644.90061
[44] G.L. Nemhauser and S. Park , A polyhedral approach to edge coloring . Oper. Res. Lett. 10 ( 1991 ) 315 - 322 . MR 1128970 | Zbl 0754.90062 · Zbl 0754.90062 · doi:10.1016/0167-6377(91)90003-8
[45] G.L. Nemhauser and L.A. Wolsey , Integer and Combinatorial Optimization . John Wiley & Sons Inc. ( 1988 ). MR 948455 | Zbl 0652.90067 · Zbl 0652.90067
[46] M.M. Passini , Um modelo de otimização combinatória para o dimensionamento de uma rede urbana de telecomunicações , M.Sc. Thesis. COPPE, Universidade Federal do Rio de Janeiro ( 1996 ).
[47] D.M. Ryan and B.A. Foster , An integer programming approach to scheduling , in Computer Scheduling of Public Transport Urban Passenger Vehicle and Crew Scheduling. North Holland ( 1981 ).
[48] C. Ribeiro , M. Minoux and M.C. Penna , An optimal column-generation-with-ranking algorithm for very large scale partitioning problems in traffic assignment . Eur. J. Oper. Res. 41 ( 1989 ) 232 - 239 . MR 1010320 | Zbl 0679.90043 · Zbl 0679.90043 · doi:10.1016/0377-2217(89)90389-5
[49] C. Ribeiro and F. Soumis , A column generation approach to the multiple-depot vehicle scheduling problem . Oper. Res. 42 ( 1994 ) 41 - 52 . Zbl 0798.90038 · Zbl 0798.90038 · doi:10.1287/opre.42.1.41
[50] M. Savelsbergh , A branch-and-price algorithm for the generalized assignment problem . Oper. Res. 46 ( 1997 ) 831 - 841 . MR 1605323 | Zbl 0895.90161 · Zbl 0895.90161 · doi:10.1287/opre.45.6.831
[51] L.G. Simonetti , Geração de colunas para o problema de empacotamento de árvores de Steiner , M.Sc. dissertation. Universidade Federal do Rio de Janeiro ( 2003 ).
[52] A. Sutter , F. Vanderbeck and L. Wolsey , Optimal placemente of add/drop multiplexers: Heuristic and exact algorithms . Oper. Res. 46 ( 1998 ) 719 - 728 . Zbl 0987.90014 · Zbl 0987.90014 · doi:10.1287/opre.46.5.719
[53] E.D. Taillard , A heuristic generation method for the heterogeneous fleet VRP . RAIRO: Oper. Res. 33 ( 1999 ) 1 - 14 . Numdam | MR 1717021 | Zbl 0992.90008 · Zbl 0992.90008 · doi:10.1051/ro:1999101
[54] F. Vanderbeck , Decomposition and Column Generation for Integer Programming , Thèse de doctorat en Sciences Appliquées. Université Catholique de Louvain, Louvain, Belgique ( 1994 ).
[55] P.H. Vance , Branch-and-price algorithms for the one-dimensional cutting stock problem . Comput. Optim. Appl. 9 ( 1998 ) 211 - 228 . MR 1604675 | Zbl 0897.90161 · Zbl 0897.90161 · doi:10.1023/A:1018346107246
[56] P.H. Vance , C. Barnhart , E.L. Johnson and G.L. Nemhauser , Solving binary cutting stock problems by column generation and branch-and-bound . Comput. Optim. Appl. 3 ( 1994 ) 111 - 130 . MR 1273657 | Zbl 0801.90080 · Zbl 0801.90080 · doi:10.1007/BF01300970
[57] P.H. Vance , C. Barnhart , E.L. Johnson and G.L. Nemhauser , Airline crew scheduling: A new formulation and decomposition algorithm . Oper. Res. 45 ( 1997 ) 188 - 200 . Zbl 0891.90087 · Zbl 0891.90087 · doi:10.1287/opre.45.2.188
[58] F. Vanderbeck , Computational study of a column generation algorithm for bin packing and cut stocking problems . Math. Programming 86 ( 1999 ) 565 - 594 . MR 1733743 | Zbl 0949.90066 · Zbl 0949.90066 · doi:10.1007/s101070050105
[59] F. Vanderbeck , On Dantzig-Wolfe decomposition in integer programming and ways to perform branching in a branch-and-price algorithm . Oper. Res. 48 ( 2000 ) 111 - 128 . Zbl 1106.90360 · Zbl 1106.90360 · doi:10.1287/opre.48.1.111.12453
[60] J.M. Van den Akker , J.A. Hoogeveen and S.L. van de Velde , Parallel machine scheduling by column generation . Oper. Res. 47 ( 1999 ) 862 - 872 . MR 1755187 | Zbl 0979.90051 · Zbl 0979.90051 · doi:10.1287/opre.47.6.862
[61] F. Vanderbeck and L. Wolsey , An exact algorithm for IP column generation . Oper. Res. Lett. 19 ( 1996 ) 151 - 159 . MR 1417867 | Zbl 0873.90074 · Zbl 0873.90074 · doi:10.1016/0167-6377(96)00033-8
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.