Selected Topics in Column Generation

References

• Adler I., Ülkücü A., Himmelblau D. M. On the number of iterations in Dantzig-Wolfe decomposition. Decomposition of Large Scale Problems (1973) (North-Holland, Amsterdam, The Netherlands) 181–187Google Scholar
• Agarwal Y., Mathur K., Salkin H. M. A set-partitioning-based exact algorithm for the vehicle routing problem. Networks (1989) 19:731–749Crossref, Google Scholar
• Alvelos F., Valério de Carvalho J. M. Solving multicommodity flow problems with branch-and-price. (2000) Google Scholar
• Anbil R., Forrest J. J., Pulleyblank W. R. Column generation and the airline crew pairing problem. Proc. Internat. Congress of Mathematicians Berlin (1998) 677–686Extra volume ICM Doc. Math. J. DMVGoogle Scholar
• Barahona F., Anbil R. The volume algorithm: Producing primal solutions with a subgradient method. Math. Programming (2000) 87(3):385–399Crossref, Google Scholar
• Barahona F., Anbil R. On some difficult linear programs coming from set partitioning. Discrete Appl. Math. (2002) 118(1–2):3–11Crossref, Google Scholar
• Barahona F., Jensen D. Plant location with minimum inventory. Math. Programming (1998) 83:101–111Crossref, Google Scholar
• Barnhart C., Schneur R. R. Air network design for express shipment service. Oper. Res. (1996) 44(6):852–863Link, Google Scholar
• Barnhart C., Hane C. A., Vance P. H. Integer multicommodity flow problems. Lecture Notes Econom. Math. Systems (1997) 450:17–31Crossref, Google Scholar
• Barnhart C., Hane C. A., Vance P. H. Using branch-and-price-and-cut to solve origin-destination integer multicommodity network flow problems. Oper. Res. (2000) 48(3):318–326Link, Google Scholar
• Barnhart C., Johnson E. L., Nemhauser G. L., Savelsbergh M. W. P., Vance P. H. Branch-and-price: Column generation for solving huge integer programs. Oper. Res. (1998b) 46(3):316–329Link, Google Scholar
• Barnhart C., Boland N. L., Clarke L. W., Johnson E. L., Nemhauser G. L., Shenoi R. G. Flight string models for aircraft fleeting and routing. Transportation Sci. (1998a) 32(3):208–220Link, Google Scholar
• 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, CanadaGoogle Scholar
• Benders J. F. Partitioning procedures for solving mixed-variables programming problems. Numer. Math. (1962) 4:238–252Crossref, Google Scholar
• Bixby R. E. Solving real-world linear programs: A decade and more of progress. Oper. Res. (2002) 50(1):3–15Link, Google Scholar
• Bixby R. E., Gregory J. W., Lustig I. J., Marsten R. E., Shanno D. F. Very large-scale linear programming: A case study in combining interior point and simplex methods. Oper. Res. (1992) 40(5):885–897Link, Google Scholar
• Borndörfer R., Grötschel M., Löbel A., Jäger W., Krebs H.-J. Duty scheduling in public transit. Mathematics—Key Technology for the Future (2003) (Springer-Verlag, Berlin) 653–674Google Scholar
• Bourjolly J.-M., Laporte G., Mercure H. A combinatorial column generation algorithm for the maximum stable set problem. Oper. Res. Lett. (1997) 20(1):21–29Crossref, Google Scholar
• Briant O., Lemaréchal C., Monneris K., Perrot N., Tadonki C., Vanderbeck F., Vial J.-P., Beltram C. Comparison of Kelley’s cutting plane, bundle, and proximal analytic center algorithms for use in branch-and-price. (2004) . Technical report, Université Bordeaux 1, Bordeaux, France. In preparationGoogle Scholar
• Caprara A., Fischetti M., Toth P. A heuristic method for the set covering problem. Oper. Res. (1999) 47:730–743Link, Google Scholar
• Caprara A., Fischetti M., Toth P. Algorithms for the set covering problem. Ann. Oper. Res. (2000) 98:353–371Crossref, Google Scholar
• Chu H. D., Gelman E., Johnson E. L. Solving large scale crew scheduling problems. Eur. J. Oper. Res. (1997) 97:260–268Crossref, Google Scholar
• Chvátal V.Linear Programming (1983) (W. H. Freeman and Company, New York) Google Scholar
• Crainic T. G., Rousseau J.-M. The column generation principle and the airline crew pairing problem. Infor (1987) 25:136–151Google Scholar
• Crama Y., Oerlemans A. G. A column generation approach to job grouping for flexible manufacturing systems. Eur. J. Oper. Res. (1994) 78(1):58–80Crossref, Google Scholar
• Dantzig G. B., Wolfe P. Decomposition principle for linear programs. Oper. Res. (1960) 8:101–111Link, Google Scholar
• Desaulniers G., Desrosiers J., Solomon M. M., Ribeiro C. C., Hansen P. Accelerating strategies in column generation methods for vehicle routing and crew scheduling problems. Essays and Surveys in Metaheuristics (2001b) (Kluwer, Boston, MA) 309–324Google Scholar
• Desaulniers G., Desrosiers J., Dumas Y., Solomon M. M., Soumis F. Daily aircraft routing and scheduling. Management Sci. (1997) 43(6):841–855Link, Google Scholar
• Desaulniers G., Desrosiers J., Erdmann A., Solomon M. M., Soumis F., Toth P., Vigo D. The VRP with pickup and delivery. The Vehicle Routing Problem (2001a) (SIAM, Philadelphia, PA) . SIAM Monographs on Discrete Mathematics and Applications, Chapter 9Google Scholar
• Desaulniers G., Desrosiers J., Ioachim I., Solomon M. M., Soumis F., Villeneuve D., Crainic T. G., Laporte G. A unified framework for deterministic time constrained vehicle routing and crew scheduling problems. Fleet Management and Logistics (1998) (Kluwer, Norwell, MA) 57–93Crossref, Google Scholar
• Desrochers M., Soumis F. A column generation approach to urban transit crew scheduling. Transportation Sci. (1989) 23:1–13Link, Google Scholar
• Desrochers M., Desrosiers J., Solomon M. M. A new optimization algorithm for the vehicle routing problem with time windows. Oper. Res. (1992) 40(2):342–354Link, Google Scholar
• Desrosiers J., Soumis F., Desrochers M. Routing with time windows by column generation. Networks (1984) 14:545–565Crossref, Google Scholar
• Desrosiers J., Dumas Y., Solomon M. M., Soumis F., Ball M. O., Magnanti T. L., Monma C. L., Nemhauser G. L. Time constrained routing and scheduling. Network Routing (1995) 8(North-Holland, Amsterdam, The Netherlands) 35–139Handbooks in Operations Research and Management ScienceCrossref, Google Scholar
• du Merle O., Villeneuve D., Desrosiers J., Hansen P. Stabilized column generation. Discrete Math. (1999) 194:229–237Crossref, Google Scholar
• Eben-Chaime M., Tovey C. A., Ammons J. C. Circuit partitioning via set partitoning and column generation. Oper. Res. (1996) 44(1):65–76Link, Google Scholar
• Elhallaoui I., Villeneuve D., Soumis F., Desaulniers G. Dynamic aggregation of set partitioning constraints in column generation. Oper. Res. (2005) 53(4):632–645Link, Google Scholar
• Elhedhli S., Goffin J.-L. The integration of an interior-point cutting-plane method within a branch-and-price algorithm. Math. Programming (2004) . In pressCrossref, Google Scholar
• Erdmann A., Nolte A., Noltemeier A., Schrader R. Modeling and solving an airline schedule generation problem. Ann. Oper. Res. (2001) 107:117–142Crossref, Google Scholar
• Farley A. A. A note on bounding a class of linear programming problems, including cutting stock problems. Oper. Res. (1990) 38(5):922–923Link, Google Scholar
• Ford L. R., Fulkerson D. R. A suggested computation for maximal multicommodity network flows. Management Sci. (1958) 5:97–101Link, Google Scholar
• Forrest J. J., Goldfarb D. Steepest-edge simplex algorithms for linear programming. Math. Programming (1992) 57:341–374Crossref, Google Scholar
• Gamache M., Soumis F., Marquis G., Desrosiers J. A column generation apporach for large-scale aircrew rostering problems. Oper. Res. (1999) 47(2):247–263Link, Google Scholar
• Gamache M., Soumis F., Villeneuve D., Desrosiers J., Gélinas E. The preferential bidding system at Air Canada. Transportation Sci. (1998) 32(3):246–255Link, Google Scholar
• Geoffrion A. M. Lagrangean relaxation for integer programming. Math. Programming Stud. (1974) 2:82–114Crossref, Google Scholar
• Gilmore P. C., Gomory R. E. A linear programming approach to the cutting-stock problem. Oper. Res. (1961) 9:849–859Link, Google Scholar
• Gilmore P. C., Gomory R. E. A linear programming approach to the cutting stock problem—Part II. Oper. Res. (1963) 11:863–888Link, Google Scholar
• Goffin J.-L., Vial J.-Ph. Convex nondifferentiable optimization: A survey focused on the analytic center cutting plane method. Optim. Methods Software (2003) 17:805–867Crossref, Google Scholar
• Goffin J.-L., Haurie A., Vial J.-Ph., Zhu D. L. Using central prices in the decomposition of linear programs. Eur. J. Oper. Res. (1993) 64:393–409Crossref, Google Scholar
• Goldfarb D., Reid J. K. A practicable steepest-edge simplex algorithm. Math. Programming (1977) 12:361–371Crossref, Google Scholar
• Grötschel M., Lovász L., Schrijver A.Geometric Algorithms and Combinatorial Optimization (1988) (Springer, Berlin, Germany) Crossref, Google Scholar
• Hadjar A., Marcotte O., Soumis F. A branch-and-cut algorithm for the multiple depot vehicle scheduling problem. (2001) . Les Cahiers du GERAD G-2001-25, HEC, Montréal, Québec, CanadaGoogle Scholar
• Hansen P., Jaumard B., Poggi de Aragão M. Mixed-integer column generation algorithms and the probabilistic maximum satisfiability problem. Eur. J. Oper. Res. (1998) 108:671–683Crossref, Google Scholar
• Harris P. M. J. Pivot selection methods of the Devex LP code. Math. Programming (1973) 5:1–28Crossref, Google Scholar
• Hiriart-Urruty J.-B., Lemaréchal C.Convex Analysis and Minimization Algorithms, Part 2: Advanced Theory and Bundle Methods (1993) 306(Springer, Berlin, Germany) . Grundlehren der mathematischen WissenschaftenGoogle Scholar
• Ho J. K. Convergence behavior of decomposition algorithms for linear programs. Oper. Res. Lett. (1984) 3(2):91–94Crossref, Google Scholar
• Holm S., Tind J. A unified approach for price directive decomposition procedures in integer programming. Discrete Appl. Math. (1988) 20:205–219Crossref, Google Scholar
• Holmberg K., Jörnsten K. A simple modification of Dantzig-Wolfe decomposition. Optimization (1995) 34(2):129–145Crossref, Google Scholar
• Hurkens C. A. J., De Jong J. L., Chen Z. A branch-and-price algorithm for solving the cutting strips problem. Appl. Math., Ser. B (1997) 12(2):215–224(English ed.)Crossref, Google Scholar
• Ioachim I., Desrosiers J., Soumis F., Bélanger N. Fleet assignment and routing with schedule synchronization constraints. Eur. J. Oper. Res. (1999) 119(1):75–90Crossref, Google Scholar
• Ioachim I., Gélinas S., Soumis F., Desrosiers J. A dynamic programming algorithm for the shortest path problem with time windows and linear node costs. Networks (1998) 31:193–204Crossref, Google Scholar
• Irnich S., Villeneuve D. The shortest path problem with resource constraints and k-cycle elimination for k ≥ 3. INFORMS J. Comput. (2003) . ForthcomingGoogle Scholar
• Johnson E. L., Wallace S. W. Modelling and strong linear programs for mixed integer programming. Algorithms and Model Formulations in Mathematical Programming (1989) (Springer, Berlin, Germany) 1–43Crossref, Google Scholar
• Johnson E. L., Mehrotra A., Nemhauser G. L. Min-cut clustering. Math. Programming (1993) 62:133–151Crossref, Google Scholar
• Kallehauge B., Larsen J., Madsen O. B. G. Lagrangean duality applied on vehicle routing with time windows. (2001) . Technical report IMM-TR-2001-9, Informatics and Mathematical Modelling, Technical University of Denmark, Kgs. Lyngby, DenmarkGoogle Scholar
• Kantorovich L. V. Mathematical methods of organising and planning production. Management Sci. (1960) 6:366–422Translation from Russian original 1939Link, Google Scholar
• Kelley J. E. The cutting-plane method for solving convex programs. J. Soc. Indust. Appl. Math. (1961) 8(4):703–712Crossref, Google Scholar
• Kim K., Nazareth J. L. The decomposition principle and algorithms for linear programming. Linear Algebra Appl. (1991) 152:119–133Crossref, Google Scholar
• Kirkeby Martinson R., Tind J. An interior point method in Dantzig-Wolfe decomposition. Comput. Oper. Res. (1999) 26(12):1195–1216Crossref, Google Scholar
• Klein P., Young N. On the number of iterations for Dantzig-Wolfe optimization and packing-covering approximation algorithms. Proc. 7th Internat. IPCO Conf. (1999) Graz, Austria(Springer, Berlin, Germany) 320–327Lecture Notes in Computer Science, No. 1610Crossref, Google Scholar
• Kohl N., Madsen O. B. G. An optimization algorithm for the vehicle routing problem with time windows. Oper. Res. (1997) 45:395–406Link, Google Scholar
• Kohl N., Desrosiers J., Madsen O. B. G., Solomon M. M., Soumis F. 2-path cuts for the vehicle routing problem with time windows. Transportation Sci. (1999) 33(1):101–116Link, Google Scholar
• Krumke S. O., Rambau J., Torres L. M., Möhring R. H., Raman R. Real-time dispatching of guided and unguided automobile service units with soft time windows. Proc. 10th Annual Eur. Sympos. Algorithms (2002) Rome, Italy(Springer, Berlin, Germany) 637–648Lecture Notes in Computer Science, 2461Crossref, Google Scholar
• Lasdon L. S.Optimization Theory for Large Systems (1970) (Macmillan, London, UK) Google Scholar
• Löbel A. Optimal vehicle scheduling in public transit. (1997) . Ph.D. thesis, Technische Universität Berlin, Berlin, GermanyGoogle Scholar
• Löbel A. Vehicle scheduling in public transit and Lagrangean pricing. Management Sci. (1998) 44(12):1637–1649Link, Google Scholar
• Lübbecke M. E., Zimmermann U. T. Engine routing and scheduling at industrial in-plant railroads. Transportation Sci. (2003) 37(2):183–197Link, Google Scholar
• Madsen K. An algorithm for minimax solution of overdetermined systems of non-linear equations. J. Inst. Math. Appl. (1975) 16:321–328Crossref, Google Scholar
• Mahey P. A subgradient algorithm for accelerating the Dantzig-Wolfe decomposition method. Proc. X. Sympos. Oper. Res., Part I: Sections 1–5. Methods in Operations Research (1986) 697–70753 Königstein/Ts., Athenäum/Hain/Scriptor/HansteinGoogle Scholar
• Mamer J. W., McBride R. D. A decomposition-based pricing procedure for large-scale linear programs—An application to the linear multicommodity flow problem. Management Sci. (2000) 46(5):693–709Link, Google Scholar
• Marquardt D. W. An algorithm for least-squares estimation of nonlinear parameters. SIAM J. Appl. Math. (1963) 11:431–441Crossref, Google Scholar
• Marsten R. E. The use of the boxstep method in discrete optimization. Math. Programming Stud. (1975) 3:127–144Crossref, Google Scholar
• Marsten R. E., Hogan W. W., Blankenship J. W. The method for large-scale optimization. Oper. Res. (1975) 23:389–405Link, Google Scholar
• Mehlhorn K., Ziegelmann M. Resource constrained shortest paths. Proc. 8th Annual Eur. Sympos. Algorithms (2000) Saarbrücken, Germany(Springer, Berlin, Germany) 326–337Lecture Notes in Computer Science, 1879Crossref, Google Scholar
• Mehrotra A., Trick M. A. A column generation approach for graph coloring. INFORMS J. Comput. (1996) 8(4):344–354Link, Google Scholar
• Minoux M.Mathematical Programming (1986) (John Wiley and Sons, Chichester, UK) Google Scholar
• Minoux M. A class of combinatorial problems with polynomially solvable large scale set covering/partitioning relaxations. RAIRO Rech. Opér. (1987) 21:105–136Crossref, Google Scholar
• Nazareth J. L. Numerical behaviour of LP algorithms based upon the decomposition principle. Linear Algebra Appl. (1984) 57:181–189Crossref, Google Scholar
• Nazareth J. L.Computer Solution of Linear Programs (1987) (Oxford University Press, Oxford, UK) Google Scholar
• Nemhauser G. L., Wolsey L. A.Integer and Combinatorial Optimization (1988) (John Wiley and Sons, Chichester, UK) Crossref, Google Scholar
• Park K., Kang S., Park S. An integer programing approach to the bandwidth packing problem. Management Sci. (1996) 42(9):1277–1291Link, Google Scholar
• Poggi de Aragão M., Uchoa E. Integer program reformulation for robust branch-and-cut-and-price algorithms. Proc. Conf. Math. Program in Rio: A Conf. in Honour of Nelson Maculan (2003) Rio de Janeiro, Brazil:56–61Google Scholar
• Ribeiro C. C., Soumis F. A column generation approach to the multiple-depot vehicle scheduling problem. Oper. Res. (1994) 42(1):41–52Link, Google Scholar
• Ribeiro C. C., Minoux M., Penna M. C. An optimal column-generation-with-ranking algorithm for very large scale set partitioning problems in traffic assignment. Eur. J. Oper. Res. (1989) 41:232–239Crossref, Google Scholar
• Ryan D. M., Foster B. A., Wren A. An integer programming approach to scheduling. Computer Scheduling of Public Transport Urban Passenger Vehicle and Crew Scheduling (1981) (North-Holland, Amsterdam, The Netherlands) 269–280Google Scholar
• Sankaran J. K. Column generation applied to linear programs in course registration. Eur. J. Oper. Res. (1995) 87(2):328–342Crossref, Google Scholar
• Savelsbergh M. W. P. A branch-and-price algorithm for the generalized assignment problem. Oper. Res. (1997) 45(6):831–841Link, Google Scholar
• Savelsbergh M. W. P., Sol M. DRIVE: Dynamic routing of independent vehicles. Oper. Res. (1998) 46(4):474–490Link, Google Scholar
• Schrijver A.Theory of Linear and Integer Programming (1986) (John Wiley and Sons, Chichester, UK) Google Scholar
• Senne E. L. F., Lorena L. A. N. Stabilizing column generation using Lagrangean/surrogate relaxation: An application to p-median location problems. (2001) EURO 2001—The European Operational Res. ConferenceErasmus University Rotterdam, July 9–11Google Scholar
• Sol M. Column generation techniques for pickup and delivery problems. (1994) . Ph.D. thesis, Eindhoven University of Technology, Eindhoven, The NetherlandsGoogle Scholar
• Soumis F., Dell’Amico M., Maffioli F., Martello S. Decomposition and column generation. Annotated Bibliographies in Combinatorial Optimization (1997) (John Wiley and Sons, Chichester, UK) 115–126Google Scholar
• Swoveland C. A note on column generation in Dantzig-Wolfe decomposition algorithms. Math. Programming (1974) 6:365–370Crossref, Google Scholar
• Valério de Carvalho J. M. Exact solution of bin-packing problems using column generation and branch-and-bound. Ann. Oper. Res. (1999) 86:629–659Crossref, Google Scholar
• Valério de Carvalho J. M. Using extra dual cuts to accelerate column generation. (2000) . Technical report, Dept. Produção e Sistemas, Universidade do Minho, Braga, Portugal. INFORMS J. Comput. ForthcomingGoogle Scholar
• Valério de Carvalho J. M. LP models for bin-packing and cutting stock problems. Eur. J. Oper. Res. (2002a) 141(2):253–273Crossref, Google Scholar
• Valério de Carvalho J. M. A note on branch-and-price algorithms for the one-dimensional cutting stock problem. Comput. Optim. Appl. (2002b) 21(3):339–340Crossref, Google Scholar
• Van Roy T. J. Cross decomposition for mixed integer programming. Math. Programming (1983) 25:46–63Crossref, Google Scholar
• Vance P. H. Branch-and-price algorithms for the one-dimensional cutting stock problem. Comput. Optim. Appl. (1998) 9(3):211–228Crossref, Google Scholar
• Vance P. H., Barnhart C., Johnson E. L., Nemhauser G. L. Solving binary cutting stock problems by column generation and branch-and-bound. Comput. Optim. Appl. (1994) 3(2):111–130Crossref, Google Scholar
• Vanderbeck F. Decomposition and column generation for integer programs. (1994) . Ph.D. thesis, Université Catholique de Louvain, Louvain-la-Neuve, BelgiumGoogle Scholar
• Vanderbeck F. Computational study of a column generation algorithm for bin packing and cutting stock problems. Math. Programming (1999) 86(3):565–594Crossref, Google Scholar
• Vanderbeck F. On Dantzig-Wolfe decomposition in integer programming and ways to perform branching in a branch-and-price algorithm. Oper. Res. (2000) 48(1):111–128Link, Google Scholar
• Vanderbeck F., Desaulniers G., Desrosiers J., Solomon M. M. Implementing mixed integer column generation. Column Generation (2005) (Springer-Verlag, Boston, MA) Crossref, Google Scholar
• Vanderbeck F., Wolsey L. A. An exact algorithm for IP column generation. Oper. Res. Lett. (1996) 19:151–159Crossref, Google Scholar
• Villeneuve D. Logiciel de génération de colonnes. (1999) . Ph.D. thesis, École Polytechnique de Montréal, Montréal, Québec, CanadaGoogle Scholar
• Villeneuve D., Desrosiers J., Lübbecke M. E., Soumis F. On compact formulations for integer programs solved by column generation. Ann. Oper. Res. (2005) 139(1):375–388Crossref, Google Scholar
• Walker W. E. A method for obtaining the optimal dual solution to a linear program using the Dantzig-Wolfe decomposition. Oper. Res. (1969) 17:368–370Link, Google Scholar
• Wedelin D. An algorithm for large scale 0-1 integer programming with application to airline crew scheduling. Ann. Oper. Res. (1995) 57:283–301Crossref, Google Scholar
• Wentges P. Weighted Dantzig-Wolfe decomposition of linear mixed-integer programming. Internat. Trans. Oper. Res. (1997) 4(2):151–162Crossref, Google Scholar
• Wilhelm W. E. A technical review of column generation in integer programming. Optim. and Engrg. (2001) 2:159–200Crossref, Google Scholar
• Wolsey L. A.Integer Programming (1998) (John Wiley and Sons, Chichester, UK) Google Scholar