Progress in Linear Programming-Based Algorithms for Integer Programming: An Exposition

References

• Anbil R., Forrest J.J., Pulleyblank W.R. Column Generation and the Airline Crew Pairing Problem. Documenta Mathematica (1998) III:677–686Google Scholar
• Anbil R., Tanga R., Johnson E. A Global Optimization Approach to Crew Scheduling. IBM Systems Journal (1991) 31:71–78Crossref, Google Scholar
• Applegate D., Bixby R.E., Chvatal V., Cook W.J. ABCC TSP, 16th International Symposium on Mathematical Programming. (1997) (Lausanne, Switserland)Google Scholar
• Arntzen B.C., Brown G.B., Harrison T.P., Trafton L.L. Global Supply Chain Management at Digital Equipment Corporation. Interfaces (1995) 25:69–93Link, Google Scholar
• Balas E., Ceria S., Cornuejols G. A Lift-and-Project Cutting Plane Algorithm for Mixed 0-1 Programs. Mathematical Programming (1993) 58:295–324Crossref, Google Scholar
• Balas E., Ceria S., Cornuejols G., Natraj N. Gomory Cuts Revisited. Operations Research Letters (1996) 19:1–9Crossref, Google Scholar
• Balas E., Ceria S., Dawande M., Margot F., Pataki G. Octane: A New Heuristic for Pure 0-1 Programs. Operations Researchin pressGoogle Scholar
• Balas E., Martin R. Pivot and Complement: A Heuristic for 0-1 Programming. Management Science (1980) 26:86–96Link, Google Scholar
• Barnhart C., Johnson E.L., Anbil R., Hatay L., Ciriani T.A., Leachman R.C. A Column Generation Technique for the Long-Haul Crew Assignment Problem. Optimization in Industry II (1994) (Wiley, Chichester) 7–24Google Scholar
• Barnhart C., Johnson E.L., Nemhauser G.L., Savelsbergh M.W.P., Vance P.H. Branch-and-Price: Column Generation for Solving Integer Programs. Operations Research (1998) 46:316–329Link, Google Scholar
• Barnhart C., Johnson E.L., Nemhauser G.L., Vance P.H., Hall R.W. Crew Scheduling. Handbook of Transportation Science (1999) (Kluwer, Boston) 493–521Crossref, Google Scholar
• Beale E.M.L., Hammer P.L., Johnson E.L., Korte B.H. Branch and Bound Methods for Mathematical Programming Systems. Discrete Optimization II (1979) (North-Holland, Amsterdam) 201–219Crossref, Google Scholar
• Bénichou M., Gauthier J.M., Girodet P., Hentges G., Ribiere G., Vincent O. Experiments in Mixed-Integer Linear Programming. Mathematical Programming (1971) 1:76–94Crossref, Google Scholar
• Bertsimas D., Darnell C., Soucy R. Portfolio Construction Through Mixed-Integer Programming at Grantham, Mayo, Van Otterloo and Company. Interfaces (1999) 29:49–66Link, Google Scholar
• Birge J., Louveaux F.Introduction to Stochastic Programming (1997) (Springer-Verlag, New York) Google Scholar
• Bisschop J., Entriken R.AIMMS The Modeling System (1993) (Paragon Decision Technology)Google Scholar
• Bixby R.E., Boyd E.A., Dadmehr S.S., Indovina R.R. The MIPLIB Mixed Integer Programming Library, Technical Report R92-36. (1992) (Rice University, Houston, Texas) Google Scholar
• Bixby R.E., Ceria S., Mczeal C., Savelsbergh M.W.P. An Updated Mixed Integer Programming Library: MIPLIB 3.0. Optima (1998) 58:12–15Google Scholar
• Bixby R.E., Cook W., Cox A., Lee E. Parallel Mixed Integer Programming. (1995) (Rice University, Houston, Texas) . Technical Report CRPC-TR5554Google Scholar
• Boehning R.L., Butler R.M., Gillett B.E. A Parallel Integer Linear Programming Algorithm. European Journal of Operations Research (1988) 34:393–398Crossref, Google Scholar
• Botha S., Gryffenberg I., Hofmeyr F.R., Lausberg J.L., Nicolay R.P., Smit W.J., Uys S., Van Der Merwe W.L., Wessels G.J. Guns or Butter: Decision Support for Determining the Size and Shape of the South African National Defense Force. Interfaces (1997) 27:7–28Link, Google Scholar
• Brearley A.L., Mitra G., Williams H.P. Analysis of Mathematical Programming Problems Prior to Applying the Simplex Algorithm. Mathematical Programming (1975) 8:54–83Crossref, Google Scholar
• Brooke A., Kendrick D., Meeraus A.GAMS, A User's Guide (1988) (Scientific Press, Redwood City, CA) Google Scholar
• Camm J.D., Chorman T.E., Dill F.A., Evans J.R., Sweeney D.J., Wergryn G.W. Blending OR/MS, Judgement, and GIS: Restructuring P&G's Supply Chain. Interfaces (1997) 27:128–142Link, Google Scholar
• Cannon T.L., Hoffman K.L. Large-Scale 0-1 Programming on Distributed Workstations. Annals of Operations Research (1990) 22:181–217Crossref, Google Scholar
• Caprara A., Fischetti M., Dell'Amico M., Maffioli F., Martello S. Branch-and-Cut Algorithms. Annotated Bibliographies in Combinatorial Optimization (1997) (Wiley, Chichester) 45–63Google Scholar
• Chvátal V. Edmonds Polytopes and a Hierarchy of Combinatorial Problems. Discrete Mathematics (1973) 4:305–327Crossref, Google Scholar
• Chvátal V. Edmonds Polytopes and Weakly Hamiltonian Graphs. Mathematical Programming (1973) 5:29–40Crossref, Google Scholar
• Cornuejols G., Dawande M., Bixby R.E., Boyd E.A., Rios-Mercado R.Z. A Class of Hard Small 0-1 Programs. Proceedings of the 6th International IPCO Conference (1998) (Springer-Verlag, Berlin) 284–293Crossref, Google Scholar
• CPLEX OPTIMIZATION, INC.Using the CPLEX Callable Library and CPLEX Mixed Integer Library (1994) . Version 3.0Google Scholar
• Crowder H., Johnson E., Padberg M. Solving Large-Scale Zero-One Linear Programming Problems. Operations Research (1983) 31:803–834Link, Google Scholar
• Dantzig G.B., Fulkerson D.R., Johnson S.M. Solution of a Large-Scale Traveling Salesman Problem. Operations Research (1954) 2:393–410Link, Google Scholar
• Dantzig G.B., Fulkerson D.R., Johnson S.M. On a Linear Programming, Combinatorial Approach to the Traveling Salesman Problem. Operations Research (1959) 7:58–66Link, Google Scholar
• DASH ASSOCIATESXPRESS-MP User Manual (1994) Google Scholar
• Desrosiers J., Dumas Y., Solomon M.M., Soumis F., Ball M.O., Magnanti T.L., Monma C., Nemhauser G.L. Time Constrained Routing and Scheduling. Handbooks in Operations Research and Management Science, Volume 8: Network Routing (1995) (Elsevier, Amsterdam) 35–140Google Scholar
• Dietrich B.L., Escudero L.F., Chance F. Efficient Reformulation for 0-1 Programs: Methods and Computational Results. Discrete Applied Mathematics (1993) 42:147–175Crossref, Google Scholar
• Driebeek N.J. An Algorithm for the Solution of Mixed Integer Programming Problems. Management Science (1966) 12:576–587Link, Google Scholar
• Eckstein J. Parallel Branch-and-Bound Algorithms for General Mixed Integer Programming on the CM-5. SIAM Journal on Optimization (1994) 4:794–814Crossref, Google Scholar
• Escudero L.F., Martello S., Toth P., Balas E., Clausen J. A Framework for Tightening 0-1 Programs Based on Extensions of Pure 0-1 KP and SS Problems. Proceedings of the 4th International IPCO Conference (1996) (Springer, Berlin) 110–123Google Scholar
• Forrest J.J.H., Hirst J.P.H., Tomlin J.A. Practical Solution of Large Scale Mixed Integer Programming Problems with UMPIRE. Management Science (1974) 20:736–773Link, Google Scholar
• Fourer R., Gay D.M., Kernighan B.W.AMPL: A Modeling Language for Mathematical Programming (1993) (Scientific Press, Redwood City, CA) Google Scholar
• Gendron B., Crainic T. Parallel Branch-and-Bound Algorithms: Survey and Synthesis. Operations Research (1994) 42:1042–1066Link, Google Scholar
• Glover F. (1996) . personal communicationGoogle Scholar
• Goemans M.X. Improved Approximation Algorithms for Scheduling with Release Dates. Proceedings of the 8th ACM-SIAM Symposium on Discrete Algorithms (1997) 591–598Google Scholar
• Gomory R. An Algorithm for the Mixed Integer Problem. (1960) (The Rand Corporation, Santa Monica, CA) . Technical Report RM-2597Google Scholar
• Gomory R.E. Outline of an Algorithm for Integer Solutions to Linear Programs. Bulletin of the American Mathematical Society (1958) 64:275–278Crossref, Google Scholar
• Grötschel M., Jünger M., Reinelt G. A Cutting Plane Algorithm for the Linear Ordering Problem, Operations. Research (1984) 32:1195–1220Abstract, Google Scholar
• Grötschel M., Monma C.L., Stoer M. Computational Results with a Cutting Plane Algorithm for Designing Communication Networks with Low-Connectivity Constraints. Operations Research (1992) 40:309–330Link, Google Scholar
• Grötschel M., Monma C.L., Stoer M., Ball M.O., Magnanti T.L., Monma C., Nemhauser G.L. Design of Survivable Networks. Handbooks in Operations Research and Management Science, Volume 7: Network Models (1995) (Elsevier, Amsterdam) 617–672Google Scholar
• Grötschel M., Padberg M.W. On the Symmetric Traveling Salesman Problem II: Lifting Theorems and Facets. Mathematical Programming (1979) 16:281–302Crossref, Google Scholar
• Grötschel M., Pulleyblank W.R. Clique Tree Inequalities and the Symmetric Traveling Salesman Problem. Mathematics of Operations Research (1986) 11:537–569Link, Google Scholar
• Gu Z., Nemhauser G.L., Savelsbergh M.W.P. Cover Inequalities for 0-1 Integer Programs: Computation. INFORMS Journal on Computing (1998) 10:427–437Link, Google Scholar
• Gue K., Nemhauser G.L., Padron M. Production Scheduling in Almost Continuous Time. IIE Transactions (1997) 29:341–358Crossref, Google Scholar
• Guignard M., Spielberg K. Logical Reduction Methods in Zero-One Programming. Operations Research (1981) 29:49–74Link, Google Scholar
• Hall L.A., Schuls A.S., Shmoys D.B., Wein J. Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms. Mathematics of Operations Research (1997) 22:513–544Link, Google Scholar
• Hane C., Barnhart C., Johnson E.L., Marsten R., Nemhauser G.L., Sigismondi G.C. The Fleet Assignment Problem: Solving a Large Integer Program. Mathematical Programming (1995) 70:211–232Crossref, Google Scholar
• Hoffman K., Padberg M. Improving LP-Representations of Zero-One Linear Programs for Branch-and-Cut. ORSA Journal of Computing (1991) 3:121–134Link, Google Scholar
• Hoffman K., Padberg M. Solving Airline Crew-Scheduling Problems by Branch-and-Cut. Management Science (1993) 39:667–682Link, Google Scholar
• Hueter J., Swart W. An Integrated Labor-Management System for Taco Bell. Interfaces (1998) 28:75–91Link, Google Scholar
• IBM CORPORATIONOptimization Subroutine Library, Guide and Reference (1990) Google Scholar
• Infanger G.Planning Under Uncertainty (1994) (Scientific Press, Redwood City, CA) Google Scholar
• Johnson E.L., Wallace S.W. Modeling and Strong Linear Programs for Mixed Integer Programming. Algorithms and Model Formulations in Mathematical Programming, NATO ASI Series 51 (1989) 1–41Crossref, Google Scholar
• Johnson E.L., Padberg M. Degree-Two Inequalities, Clique Facets and Biperfect Graphs. Annals of Discrete Mathematics (1982) 16:169–187Google Scholar
• Jünger M., Reinelt G., Rinaldi G., Ball M.O., Magnanti T.L., Monma C., Nemhauser G.L. The Traveling Salesman Problem. Handbooks in Operations Research and Management Science, Volume 7: Network Models (1995) (Elsevier, Amsterdam) 225–330Google Scholar
• Jünger M., Störmer P. Solving Large-Scale Traveling Salesman Problems with Parallel Branch-and-Cut. (1995) (Universität zu Köln, Cologne, Germany) . Technical Report 95.191Google Scholar
• Jünger M., Thienel S. Introduction to ABACUS: A Branch-And-Cut System. Operations Research Letters (1998) 22:83–95Crossref, Google Scholar
• Kall P., Wallace S.W.Stochastic programming (1994) (Wiley, New York) Google Scholar
• Klabjan D., Johnson E.L., Nemhauser G.L. Solving Large Airline Crew Scheduling Problems. (1999) (Georgia Institute of Technology, Atlanta, GA) . Technical Report TLI-99-11Google Scholar
• Land H.A., Doig A.G. An Automatic Method for Solving Discrete Programming Problems. Econometrica (1960) 28:497–520Crossref, Google Scholar
• Laporte G., Louveaux F.V. The Integer L-Shaped Method for Stochastic Integer Programs. Operations Research Letters (1993) 13:133–142Crossref, Google Scholar
• Lenstra H.W. Integer Programming with a Fixed Number of Variables. Mathematics of Operations Research (1983) 8:538–547Link, Google Scholar
• Linderoth J.Topics in Parallel Integer Programming (1998) (Georgia Institute of Technology, Atlanta, GA) . Ph.D. ThesisGoogle Scholar
• Linderoth J., Savelsbergh M.W.P. Search Strategies for Mixed Integer Programming. INFORMS Journal on Computing (1999) 11:173–187Link, Google Scholar
• Marchand H., Wolsey L. A. The 0-1 Knapsack Problem with a Single Continuous Variable. Mathematical Programming (1999) 85:15–33Crossref, Google Scholar
• Martin O., Otto S.W., Felten E.W. Large Step Markov Chains for the TSP Incorporating Local Search Heuristics. Operations Research Letters (1992) 11:219–224Crossref, Google Scholar
• Mehrotra A., Johnson E.L., Nemhauser G.L. An Optimization Based Heuristic for Political Districting. Management Science (1998) 44:1100–1114Link, Google Scholar
• Monma C.L., Shallcross D.F. Methods for Designing Communication Networks with Certain Two-Connected Survivability Constraints. Operations Research (1989) 37:531–541Link, Google Scholar
• Nemhauser G.L., Savelsbergh M.W.P., Sigismondi G.C. MINTO: A Mixed INTeger Optimizer. Operations Research Letters (1993) 15:47–58Crossref, Google Scholar
• Nemhauser G.L., Wolsey L.A.Integer and Combinatorial Optimization (1988) (Wiley, New York) Crossref, Google Scholar
• Padberg M.W., Rinaldi G. Optimization of a 532 City Symmetric Traveling Salesman Problem by Branch and Cut. Operations Research Letters (1987) 6:1–7Crossref, Google Scholar
• Padberg M.W., Roy T.J.V., Wolsey L.A. Valid Linear Inequalities for Fixed Charge Problems. Operations Research (1985) 33:842–861Link, Google Scholar
• Savelsbergh M.W.P. Preprocessing and Probing Techniques for Mixed Integer Programming Problems. ORSA Journal on Computing (1994) 6:445–454Link, Google Scholar
• Savelsbergh M.W.P., Uma R.M., Wein J. An Experimental Study of LP-Based Approximation Algorithms for Scheduling Problems. Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (1998) 453–462Google Scholar
• Schrijver A.Theory of Linear and Integer Programming (1986) (Wiley, Chichester) Google Scholar
• Sinha G.P., Chandrasekaran B.S., Mitter N., Dutta G., Singh S.B., Choudhury A.R., Roy P.N. Strategic and Operational Management with Optimization at Tata Steel. Interfaces (1995) 25:6–19Link, Google Scholar
• Tomlin J.A. An Improved Branch-and-Bound Method for Integer Programming. Operations Research (1971) 19:1070–1075Link, Google Scholar
• Vance P.H., Atamaturk A., Barnhart C., Gelman E., Johnson E.L., Krishna A., Mahindhara D., Nemhauser G.L., Rebello R. A Heuristic Branch-and-Price Approach for the Airline Crew Pairing Problem. (1997) (Georgia Institute of Technology, Atlanta, GA) . Technical Report LEC-97-06Google Scholar
• Vance P.H., Barnhart C., Johnson E.L., Nemhauser G.L. Airline Crew Scheduling: A New Formulation and Decomposition Algorithm. Operations Research (1997) 45:188–200Link, Google Scholar
• Williams H.P.Model Building in Mathematical Programming (1978) (Wiley, Chichester) Google Scholar
• Williams H.P., Wilson J.M. Connections Between Integer Linear Programming and Constraint Logic Programming: An Overview and Introduction to the Cluster of Articles. INFORMS Journal on Computing (1998) 10:261–264Link, Google Scholar
• Wolsey L.A.Integer Programming (1998) (Wiley, New York) Google Scholar