Branch-and-Price: Column Generation for Solving Huge Integer Programs

References

• Anbil R. , Tanga R. , Johnson E. L. A global approach to crew-pairing optimization. IBM Systems J. (1992) 31 71 78 Crossref, Google Scholar
• Appelgren L. H. A column generation algorithm for a ship scheduling problem. Transportation Sci. (1969) 3 53 68 Link, Google Scholar
• Barnhart C. , Hane C. A. , Johnson E. L. , Sigismondi G. An alternative formulation and solution strategy for multi-commodity network flow problems. Telecomm. Systems (1995) 3 239 258 Crossref, Google Scholar
• Barnhart C. , Johnson E. L. , Nemhauser G. L. , Savelsbergh M. W. P. , Vance P. , Birge J. R. , Murty K. G. Branch-and-price: Column generation for solving huge integer programs (abbreviated version). Mathematical Programming, State of the Art (1994) (Braun-Brumfield) 186 207 Google Scholar
• Balas E. , Padberg M. Set partitioning: A survey. SIAM Rev. (1976) 18 710 760 Crossref, 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. Opns. Res. (1992) 40 885 897 Link, Google Scholar
• Brooks R. , Geoffrion A. Finding Everett's lagrange multipliers by linear programming. Opns. Res. (1966) 14 1149 1153 Link, Google Scholar
• CPLEX Optimization, Inc. Using the CPLEX™ Linear Optimizer (1990) Google Scholar
• Dantzig G. B. , Van Slyke R. M. Generalized upper bounding techniques. J. Comput. System Sci. (1967) 1 213 226 Crossref, Google Scholar
• Dantzig G. B. , Wolfe P. Decomposition principle for linear programs. Opns. Res. (1960) 8 101 111 Link, Google Scholar
• Desrochers M. , Desrosiers J. , Solomon M. A new optimization algorithm for the vehicle routing problem with time windows. Opns. Res. (1992) 40 342 354 Link, Google Scholar
• Desrochers M. , Soumis F. A column generation approach to the urban transit crew scheduling problem. Transportation Sci. (1989) 23 1 13 Link, Google Scholar
• Desrosiers J. , Dumas Y. , Solomon M. M. , Soumis F. , Ball M. , et al. Time constrained routing and scheduling. Handbooks in Operations Research and Management Science (1995) 8 (Elsevier, Amsterdam) 35 140 . Network Routing Google Scholar
• Desrosiers J. , Soumis F. , Desrochers M. Routing with time windows by column generation. Networks (1984) 14 545 565 Crossref, Google Scholar
• Dumas Y. , Desrosiers J. , Soumis F. The pickup and delivery problem with time windows. Eur. J. Opns. Res. (1991) 54 7 22 Crossref, Google Scholar
• Farley A. A. A note on bounding a class of linear programming problems, including cutting stock problems. Opns. Res. (1990) 38 922 924 Link, Google Scholar
• Ford L. R. , Fulkerson D. R. A suggested computation for maximal multicommodity network flows. Management Sci. (1958) 5 97 101 Link, Google Scholar
• Geoffrion A. M. Lagrangean relaxation for integer programming. Math. Programming Stud. (1974) 2 82 114 Crossref, Google Scholar
• Guignard M. , Rosenwein M. An improved dualbased algorithm for the generalized assignment problem. Opns. Res. (1989) 37 658 663 Link, Google Scholar
• Held M. , Karp R. M. The traveling-salesman problem and minimum spanning trees. Opns. Res. (1970) 18 1138 1162 Link, Google Scholar
• Held M. , Karp R. M. The traveling-salesman problem and minimum spanning trees: Part II. Math. Programming (1971) 1 6 25 Crossref, Google Scholar
• Held M. , Wolfe P. , Crowder H. P. Validation of subgradient optimization. Math. Programming (1974) 6 62 88 Crossref, Google Scholar
• Hoffman A. J. , Kolen A. , Sakarovitch M. Totally balanced and greedy matrices. SIAM J. Algebraic and Discrete Methods (1985) 6 721 730 Crossref, Google Scholar
• Hoffman K. , Padberg M. LP-based combinatorial problem solving. Ann. O. R. (1985) 4 145 194 Crossref, Google Scholar
• IBM Corporation Optimization Subroutine Library, Guide and Reference (1990) Google Scholar
• Johnson E. L. , Wallace S. W. Modeling and strong linear programs for mixed integer programming. Algorithms and Model Formulations in Mathematical Programming (1989) 1 41 . NATO ASI Series 51 Crossref, Google Scholar
• Junger M. , Reinelt G. , Rinaldi G. , Ball M. , et al. The traveling salesman problem. Handbooks in Operations Research and Management Science (1995) 7 (Elsevier, Amsterdam) 225 330 . Network Models Google Scholar
• Krishna A. , Barnhart C. , Johnson E. L. , Mahidara D. , Nemhauser G. L. , Rebello R. , Singh A. , Vance P. H. Advanced Techniques in Crew Scheduling (1995) . Presentation at INFORMS, Los Angeles, CA Google Scholar
• Lasdon L. S. Optimization Theory for Large Systems (1970) (MacMillan, New York) Google Scholar
• Lemarechal C. , Nemhauser G. , et al. Nondifferential optimization. Handbooks in Operations Research and Management Science (1989) 1 (Elsevier, Amsterdam) 529 572 . Optimization Google Scholar
• Marsten R. Crew Planning at Delta Airlines (1994) . Presentation at Mathematical Programming Symposium XV, Ann Arbor, MI Google Scholar
• Mehrotra A. Constrained graph partitioning: Decomposition, polyhedral structure and algorithms. (1992) . Ph.D. thesis, Georgia Institute of Technology, Atlanta, GA Google Scholar
• Mehrotra A. , Trick M. A. A column generation approach for exact graph coloring. INFORMS J. Comput. (1996) 8 344 354 Link, Google Scholar
• Nemhauser G. L. , Park S. A polyhedral approach to edge coloring. O. R. Lett. (1991) 10 315 322 Crossref, Google Scholar
• Nemhauser G. L. , Savelsbergh M. W. P. , Sigismondi G. C. MINTO, a Mixed INTeger Optimizer. O. R. Lett. (1994) 15 47 58 Crossref, Google Scholar
• Nemhauser G. L. , Wolsey L. A. Integer and Combinatorial Optimization (1988) (Wiley, New York, NY) Crossref, Google Scholar
• Padberg M. W. On the facial structure of set packing polyhedra. Math. Programming (1973) 5 199 215 Crossref, Google Scholar
• Parker M. , Ryan J. A column generation algorithm for bandwidth packing. Telecomm. Systems (1994) 2 185 195 Crossref, Google Scholar
• Rosen J. B. Primal partition programming for block diagonal matrices. Numerische Mathematik (1964) 6 250 260 Crossref, 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) 269 280 Google Scholar
• Savelsbergh M. W. P. A branch-and-price algorithm for the generalized assignment problem. Opns. Res. (1997) 6 831 841 Link, Google Scholar
• Sol M. , Savelsbergh M. W. P. DRIVE: Dynamic routing of independent vehicles. Opns. Res. (1998) 46 . to appear Google Scholar
• Vance P. H. Crew scheduling, cutting stock, and column generation: Solving huge integer programs. (1993) . Ph.D. thesis, School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA 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. Computational Optim. Appl. (1994) 3 111 130 Crossref, Google Scholar
• Vance P. H. , Barnhart C. , Johnson E. L. , Nemhauser G. L. Airline crew scheduling: A new formulation and decomposition algorithm. Opns. Res. (1997) 45 188 200 Link, Google Scholar
• Vanderbeck F. Decomposition and column generation for integer programs. (1994) . Ph.D. thesis, Universite Catholique de Louvain, Belgium Google Scholar
• Vanderbeck F. On integer programming decomposition and ways to enforce integrality in the master. (1995) . Report 94-95-29, University of Cambridge, England Google Scholar
• Vanderbeck F. , Wolsey L. A. An exact algorithm for IP column generation. Opns. Res. Lett. (1996) 19 151 160 Crossref, Google Scholar