×

zbMATH — the first resource for mathematics

On compact formulations for integer programs solved by column generation. (English) Zbl 1091.90052
Summary: Column generation has become a powerful tool in solving large scale integer programs. It is well known that most of the often reported compatibility issues between pricing subproblem and branching rule disappear when branching decisions are based on imposing constraints on the subproblem’s variables. This can be generalized to branching on variables of a so-called compact formulation. We constructively show that such a formulation always exists under mild assumptions. It has a block diagonal structure with identical subproblems, each of which contributes only one column in an integer solution. This construction has an interpretation as reversing a Dantzig-Wolfe decomposition. Our proposal opens the way for the development of branching rules adapted to the subproblem’s structure and to the linking constraints.

MSC:
90C10 Integer programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Barnhart, C., C.A. Hane, and P.H. Vance. (1997). ”Integer Multicommodity Flow Problems.” Lecture Notes in Economics and Mathematical Systems 450, 17–31. · Zbl 0878.90028
[2] Barnhart, C., E.L. Johnson, G.L. Nemhauser, M.W.P. Savelsbergh, and P.H. Vance. (1998). ”Branch-and-Price: Column Generation for Solving Huge Integer Programs.” Oper. Res. 46(3), 316–329. · Zbl 0979.90092
[3] Chen, Z.-L. and W.B. Powell. (1999). ”Solving Parallel Machine Scheduling Problems by Column Generation.” INFORMS J. Computing 11, 78–94. · Zbl 1034.90506
[4] Dantzig, G.B. and P. Wolfe. (1960). ”Decomposition Principle for Linear Programs.” Oper. Res. 8, 101– 111. · Zbl 0093.32806
[5] Desaulniers, G., J. Desrosiers, I. Ioachim, M.M. Solomon, F. Soumis, and D. Villeneuve. (1998). ”A Unified Framework for Deterministic Time Constrained Vehicle Routing and Crew Scheduling Problems.” In T.G. Crainic and G. Laporte (eds.), Fleet Management and Logistics, Norwell, MA, Kluwer, pp. 57–93. · Zbl 0966.90007
[6] Desrochers, M., J.K. Lenstra, M.W.P. Savelsbergh, and F. Soumis. (1991). ”Vehicle Routing with Time Windows: Optimization and Approximation.” In B.L. Golden and A.A. Assad, (eds.), Vehicle Routing: Methods and Studies, volume 16 of Studies in Management Science and Systems, North-Holland, pp. 65–84. · Zbl 0642.90055
[7] Desrosiers, J., Y. Dumas, M.M. Solomon, and F. Soumis. (1995). ”Time Constrained Routing and Scheduling.” In M.O. Ball, T.L. Magnanti, C.L. Monma, and G.L. Nemhauser (eds.), Network Routing, volume 8 of Handbooks in Operations Research and Management Science, Amsterdam: North-Holland, pp. 35–139. · Zbl 0861.90052
[8] Desrosiers, J., F. Soumis, and M. Desrochers. (1984). ”Routing with Time Windows by Column Generation.” Networks 14, 545–565. · Zbl 0571.90088
[9] Gamache, M., F. Soumis, D. Villeneuve, J. Desrosiers, and E. Gélinas. (1998). ”The Preferential Bidding System at Air Canada.” Transportation Sci. 32(3), 246–255. · Zbl 1004.90518
[10] Gilmore, P.C. and R.E. Gomory. (1961). ”A Linear Programming Approach to the Cutting-Stock Problem.” Oper. Res. 9, 849–859. · Zbl 0096.35501
[11] Holm, S. and J. Tind. (1988). ”A Unified Approach for Price Directive Decomposition Procedures in Integer Programming.” Discrete Appl. Math. 20, 205–219. · Zbl 0655.90051
[12] Johnson, E.L. (1989). ”Modelling and Strong Linear Programs for Mixed Integer Programming.” In S.W. Wallace (ed.), Algorithms and Model Formulations in Mathematical Programming, Springer: Berlin, pp. 1–43.
[13] Kantorovich, L.V. (1960). ”Mathematical Methods of Organising and Planning Production.” Management Sci. 6, 366–422. Translation from the Russian original, dated 1939. · Zbl 0995.90532
[14] Kohl, N., J. Desrosiers, O.B.G. Madsen, M.M. Solomon, and F. Soumis. (1999). ”2-Path Cuts for the Vehicle Routing Problem with Time Windows.” Transportation Sci. 33(1), 101–116. · Zbl 1004.90015
[15] Mehrotra, A., K.E. Murphy, and M.A. Trick. (2000). ”Optimal Shift Scheduling: A Branch-and-Price approach. Naval Res. Logist. 47(3), 185–200. · Zbl 0972.90032
[16] Mehrotra, A. and M.A. Trick. (1996). ”A Column Generation Approach for Graph Coloring.” INFORMS J. Comput. 8(4), 344–354. · Zbl 0884.90144
[17] Nemhauser, G.L. and L.A. Wolsey. (1988). Integer and Combinatorial Optimization. Chichester: John Wiley & Sons. · Zbl 0652.90067
[18] Ryan, D.M. and J.C. Falkner. (1987). ”A Bus Crew Scheduling System Using a Set Partitioning Mode.” Ann. Oper. Res. 4, 39–56.
[19] Ryan, D.M. and B.A. Foster. (1981). ”An Integer Programming Approach to Scheduling.” In A. Wren (ed.), Computer Scheduling of Public Transport Urban Passenger Vehicle and Crew Scheduling, Amsterdam: North-Holland, pp. 269–280.
[20] Savelsbergh, M.W.P. (1997). ”A Branch-and-Price Algorithm for the Generalized Assignment Problem.” Oper. Res. 45(6), 831–841. · Zbl 0895.90161
[21] Schrijver, A. (1986). Theory of Linear and Integer Programming. Chichester: John Wiley & Sons. · Zbl 0665.90063
[22] Sol, M. (1994). Column Generation Techniques for Pickup and Delivery Problems. PhD thesis, Eindhoven University of Technology. · Zbl 0833.90037
[23] Sweeney, D.J. and R.A. Murphy. (1979). ”A Method of Decomposition for Integer Programs.” Oper. Res. 27, 1128–1141. · Zbl 0442.90063
[24] Valério de Carvalho, J.M. (1999). ”Exact Solution of Bin-Packing Problems Using Column Generation and Branch-and-Bound.” Ann. Oper. Res. 86, 629–659. · Zbl 0922.90113
[25] Valério de Carvalho, J.M. (2002). ”LP Models for Bin-Packing and Cutting Stock Problems.” European J. Oper. Res. 141(2), 253–273. · Zbl 1059.90095
[26] van den Akker, J.M., J.A. Hoogeveen, and S.L. van de Velde. (1999). ”Parallel Machine Scheduling by Column Generation.” Oper. Res. 47(6), 862–872. · Zbl 0979.90051
[27] Vance, P.H. (1998). ”Branch-and-Price Algorithms for the One-Dimensional Cutting Stock Problem.” Comput. Optim. Appl. 9(3), 211–228. · Zbl 0897.90161
[28] Vanderbeck, F. (1994). Decomposition and Column Generation for Integer Programs. PhD thesis, Université catholique de Louvain.
[29] Vanderbeck, F. (2000a). ”Exact Algorithm for Minimising the Number of Setups in the One-Dimensional Cutting Stock Problem.” Oper. Res. 48(6), 915–926. · Zbl 1106.90373
[30] Vanderbeck, F. (2000b). ”On Dantzig-Wolfe Decomposition in Integer Programming and Ways to Perform Branching in a Branch-and-Price Algorithm.” Oper. Res. 48(1), 111–128. · Zbl 1106.90360
[31] Vanderbeck, F. and L.A. Wolsey. (1996). ”An Exact Algorithm for IP Column Generation. Oper. Res. Lett. 19, 151–159. · Zbl 0873.90074
[32] Villeneuve, D. (1999). ”Logiciel de Génération de Colonnes.” PhD thesis, École Polytechnique de Montréal.
[33] Villeneuve, D. and G. Desaulniers. (2005). ”The Shortest Path Problem with Forbidden Paths.” European J. Oper. Res. 165(1), 97–107. · Zbl 1112.90379
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.