Branch Cut and Price References
|
||||||
A.V. Aho, J.E. Hopcroft, and J.D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley Publishing Company (1974).
M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness, W.H. Freeman and Co., San Francisco (1979).
G.H. Golub and C.F. Van Loan, Matrix Computations, The Johns Hopkins University Press, Baltimore (1989).
D.E. Knuth, The Art of Computer Programming, Volumes 1-?, Addison-Wesley Publishing Company.
D.C. Kozen, The Design and Analysis of Algorithms, Springer-Verlag, New York (1992).
R.S. Garfinkel and G.L. Nemhauser, Integer Programming, Wiley, New York (1972).
G.L. Nemhauser and L.A. Wolsey, Integer and Combinatorial Optimization, John Wiley & Sons, Inc. (1988).
A. Schrijver, Theory of Linear and Integer Programming, John Wiley & Sons (1986).
General Branch, Cut, and Price References
K. Aardal and C. van Hoesel, Polyhedral Techniques in Combinatorial Optimization I: Theory, Statistica Neerlandica 50 (1996), 3.
K. Aardal and C. van Hoesel, Polyhedral Techniques in Combinatorial Optimization II: Applications and Computations, Statistica Neerlandica 50 (1996), 3.
E. Balas, An Additive Algorithm for Solving Linear Programs with Zero-One Variables, Operations Research 13 (1965), 517.
E. Balas, S. Ceria and G. Cornuéjols, Mixed 0-1 Programming by Lift-and-Project in a Branch-and-cut Framework, Management Science 42 (1996), 9.
E. Balas, S. Ceria, G. Cornuéjols, and N. Natraj , Gomory Cuts Revisited . Operations Research Letters 19, 1.
E. Balas and P. Toth, Branch and Bound Methods, in E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan and D.B. Shmoys, eds., The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, Wiley, New York (1985), 361.
C. Barnhart, E.L. Johnson, G.L. Nemhauser, M.W.P. Savelsbergh, P.H. Vance, Branch-and-Price: Column Generation for Huge Integer Programs, Operations Research 46 (1998), 316-329.
E. Beale, Branch and Bound Methods for Mathematical Programming Systems, Annals of Discrete Mathematics 5 (1979), 201.
A. Caprara and M. Fishetti, Branch-and-cut Algorithms, in M. Dell'Amico, F. Maffioli, and S. Martello, editors, Annotated Bibliographies in Combinatorial Optimization (1997).
C. Cordier, H. Marchand, R. Laundy, L.A. Wolsey, bc-opt: A Branch-and-Cut Code for Mixed Integer Programs, Mathematical Programming 86 (1999), 335.
R. Dakin, A Tree-Search Algorithm for Mixed Integer Programming Problems, The Computer Journal 8 (1964), 250.
R. Gomory, Outline of an Algorithm for Integer Solutions to Linear Programs, Bulletin of the American Mathematical Society 64 (1958), 275.
M. Grötschel, L. Lovász, and A. Schrijver, The Ellipsoid Method and its Consequences in Combinatorial Optimization, Combinatorica 1 (1981), 169.
M. Grötschel, L. Lovász, and A. Schrijver, Corrigendum to our Paper "The Ellipsoid Method and its Consequences in Combinatorial Optimization", Combinatorica 4 (1984), 291.
K. Hoffman and M. Padberg, LP-Based Combinatorial Problem Solving, Annals of Operations Research 4 (1985/86), 145.
Jünger and S. Thienel, The ABACUS System for Branch and Cut and Price Algorithms in Integer Programming and Combinatorial Optimization, Technical Report No. 98.322 (1998), Universität Köln.
M. Jünger, G. Reinelt, and S. Thienel, Practical Problem Solving with Cutting Plane Algorithms in Combinatorial Optimization, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, American Mathematical Society (1995), 111.
L. Ladányi, T.K. Ralphs, and L.E. Trotter Jr. , Branch, Cut, and Price: Sequential and Parallel , in Computational Combinatorial Optimization, D. Naddef and M. Juenger, eds., Springer, Berlin (2001), 223.
A. Land and A. Doig , An Automatic Method of Solving Discrete Programming Problems, Econometrica 28 (1960), 497.
J. Linderoth, M.W.P. Savelsbergh . Computational Study of Search Strategies for Mixed Integer Programming . INFORMS Journal on Computing 11 (1999), 173-187.
A. Martin, General Mixed Integer Programming: Computational Issues for Branch-and-Cut Algorithms , in Computational Combinatorial Optimization, D. Naddef and M. Juenger, eds., Springer, Berlin (2001), 1.
H. Marchand, A. Martin, R. Wesimantel, and L. Wolsey, Cutting planes in integer and mixed integer programming, CORE Discussion paper 9953 (1999).
G.L. Nemhauser, M.W.P. Savelsbergh, G.S. Sigismondi, MINTO, a Mixed INTeger Optimizer, Operations Research Letters 15 (1994), 47-58.
T.K. Ralphs, SYMPHONY Version 2.8 User's Guide, available at www.branchandcut.org/SYMPHONY.
M. Savelsbergh, Preprocessing and Probing Techniques for Mixed Integer Programming Problems, ORSA Journal on Computing 6 (1994), 445.
D. Applegate, R. Bixby, V. Chvátal, W. Cook, On the solution of traveling salesman problems, Documenta Mathematica Journal der Deutschen Mathematiker-Vereinigung, International Congress of Mathematicians (1998), 645-656.
D. Applegate, R. Bixby, V. Chvátal, and W. Cook, CONCORDE TSP Solver, available at www.keck.caam.rice.edu/concorde.html.
D. Applegate, R. Bixby, V. Chvátal, and W. Cook, Finding Cuts in the TSP, DIMACS Technical Report 95-05 (1995).
P. Augerat, J.M. Belenguer, E. Benavent, A. Corberán, D. Naddef, G. Rinaldi , Computational Results with a Branch and Cut Code for the Capacitated Vehicle Routing Problem, Research Report 949-M, Universite Joseph Fourier, Grenoble, France.
U. Blasum and W. Hochstättler, Application of the Branch and Cut Method to the Vehicle Routing Problem, Zentrum für Angewandte Informatik Köln Technical Report zpr2000-386 (2000).
G. Dantzig, R. Fulkerson, and S. Johnson, Solution of a Large-Scale Traveling-Salesman Problem, Operations Research 2 (1954), 393.
M. Grötschel, M. Jünger, and G. Reinelt, A Cutting Plane Algorithm for the Linear Ordering Problem, Operations Research 32 (1984), 1155.
L. Hall, Experience with a Cutting Plane Algorithm for the Capacitated Spanning Tree Problem, INFORMS Journal on Computing 3 (1996), 219.
J. Little, K. Murty, D. Sweeney, and C. Karel, An Algorithm for the Traveling Salesman Problem, Operations Research 11 (1963), 972.
D. Naddef and G. Rinaldi, Branch and Cut, in P. Toth and D. Vigo, eds., Vehicle Routing, SIAM (2000).
M. Padberg and G. Rinaldi, A Branch-and-Cut Algorithm for the Resolution of Large-Scale Traveling Salesman Problems, SIAM Review 33 (1991), 60.
T.K. Ralphs, L. Kopman, W.R. Pulleyblank, and L.E. Trotter Jr., On the Capacitated Vehicle Routing Problem, Mathematical Programming, to appear.
M.W.P. Savelsbergh, A Branch-and-Price Algorithm for the Generalized Assignment Problem, Operations Research 45 (1997), 831-841.
G.M. Amdahl, Validity of the Single-processor Approach to Achieving Large-scale Computing Capabilities, In AFIPS Conference Proceedings 30 (Atlantic City, N.J., April 18-20), AFIPS Press (1967).
M. Benchouche, V.-D. Cung, S. Dowaji, B. Le Cun, T. Mautor, and C. Roucairol, Building a Parallel Branch and Bound Library, in Solving Combinatorial Optimization Problems in Parallel, Lecture Notes in Computer Science 1054, Springer, Berlin (1996), 201.
R.L. Boehning R.M. Butler and B.E. Gillet, A Parallel Integer Linear Programming Algorithm, European Journal of Operations Research 34 (1988).
V.-D. Cung, S. Dowaji, B. Le Cun, T. Mauthor and C. Roucairol, Concurrent Data Structures and Load Balancing Strategies for Parallel Branch and Bound/A* Algorithms, DIMACS Series in Discrete Optimization and Theoretical Computer Science 30 (1997).
J. Eckstein, Parallel Branch and Bound Algorithms for General Mixed Integer Programming on the CM-5, SIAM Journal on Optimization 4 (1994).
J. Eckstein, How Much Communication Does Parallel Branch and Bound Need?, INFORMS Journal on Computing 9 (1997).
J. Eckstein, C.A. Phillips and W.E. Hart, PICO: An Object-Oriented Framework for Parallel Branch and Bound, RUTCOR Research Report 40-2000.
A. Geist et al., PVM: Parallel Virtual Machine, A User's Guide and Tutorial for Networked Parallel Computing, MIT Press, Cambridge, MA (1994).
B. Gendron and T.G. Crainic, Parallel Branch and Bound Algorithms: Survey and Synthesis, Operations Research 42 (1994), 1042.
A. Grama and V. Kumar, Parallel Search Algorithms for Discrete Optimization Problems, ORSA Journal on Computing 7 (1995).
J.L. Gustafson, Reevaluating Amdahl's Law, Communications of the ACM {\bf 31} (1988).
V. Kumar and V.N. Rao, Parallel Depth-first Search. Part II. Analysis., International Journal of Parallel Programming 16 (1987).
V. Kumar and A. Gupta, Analyzing Scalability of Parallel Algorithms and Architectures, Journal of Parallel and Distributed Computing 22 (1994).
L. Ladányi, T.K.Ralphs, and M.J. Saltzman, Implementing Scalable Parallel Search Algorithms for Data-intensive Applications, The Proceedings of the International Conference on Computational Science (2002).
P. Laursen, Can Parallel Branch and Bound without Communication Be Effective?, 4 (1994).
J. Linderoth, Topics in Parallel Integer Optimization, Ph.D. Dissertation, School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA (1998).
T.K.Ralphs, L. Ladányi, and M.J. Saltzman, Parallel Branch and Bound for Large-scale Discrete Optimization, in review, available from http://www.lehigh.edu/~tkr/pubs.html .
T.K. Ralphs, Parallel Branch and Cut for Vehicle Routing, in review, available from http://www.lehigh.edu/~tkr/pubs.html.
T.K. Ralphs, SYMPHONY Version 2.8 User's Guide, available at www.branchandcut.org/SYMPHONY.
V.N. Rao and V. Kumar, Parallel Depth-first Search. Part I. Implementation., International Journal of Parallel Programming 16 (1987).
R. Rushmeier and G. Nemhauser, Experiments with Parallel Branch and Bound Algorithms for the Set Covering Problem, Operations Research Letters 13 (1993).
Y. Shinano, M. Higaki, and R. Hirabayashi, Generalized Utility for Parallel Branch and Bound Algorithms, Proceedings of the 1995 Seventh Symposium on Parallel and Distributed Processing, IEEE Computer Society Press, Los Alamitos, CA (1995), 392.
Y. Shinano, K. Harada, and R. Hirabayashi, Control Schemes in a Generalized Utility for Parallel Branch and Bound, Proceedings of the 1997 Eleventh International Parallel Processing Symposium, IEEE Computer Society Press, Los Alamitos, CA (1997), 621.
S. Tschöke and T. Polzer, Portable Parallel Branch and Bound Library User Manual, Library Version 2.0, Department of Computer Science, University of Paderborn.
This page maintained by Ted Ralphs (ted@branchandcut.org)
Last updated August 1, 2002