% Copyright 1994 by Brian Borchers. This file may be freely duplicated % and distributed so long as no consideration is received in return, and % this copyright notice remains intact. % % My Bibliography of papers and books on combinatorial optimization. % % Names of some commonly referenced journals. % @string{opsres = "Operations Research"} @string{mathprog = "Mathematical Programming"} @string{mathor = "Mathematics of Operations Research"} @string{mgmtsci = "Management Science"} @string{mathprogstud = "Mathematical Programming Study"} @string{aiietrans = "AIIE Transactions"} @string{siamjappl = "SIAM Journal on Applied Mathematics"} @string{europs = "European Journal of Operational Research"} @string{andiscrete = "Annals of Discrete Mathematics"} @string{bstj = "Bell System Technical Journal"} % % % @article{BMW:dualascent, Author="Balakrishnan, A. and T.L. Magnanti and R.T. Wong", Title="A Dual-Ascent Procedure for Large-Scale Uncapactitated Network Design", journal=opsres, year=1989, volume=37, number=5, pages="716--740" } @article{BBI:miplib, Author="Robert E. Bixby and E. Andrew Boyd and Ronni R. Indovina", Title="{MIPLIB}: A Test Set of Mixed Integer Programming Problems", journal="SIAM News", year=1992, volume=25, number=20, month="March", pages="16" } @article{Bala:nwd, Author="A. Balakrishnan", Title="{LP} Extreme Points and Cuts for the Fixed Charge Network Design Problem", journal=mathprog, volume=39, year=1987, pages="263-284", } @article{BGGHRV:experiments, Author="M. Benichou and J. M. Gauthier and P. Girodet and G. Hentges and G. Ribiere and D. Vincent", title="Experiments in Mixed Integer Linear Programming", journal=mathprog, year=1971, volume=1, pages="76--94"} @inproceedings{BS:bandb, Author="E. Beale and R. Small", Title="Mixed Integer Programming by a Branch and Bound Technique", booktitle="Proceedings of the Third IFIP Congress", pages="450-451", year=1965} @article{beasley:alg, author="J. E. Beasley", title="An algorithm for solving large capacitated warehouse location problems", journal=europs, year=1988, volume=33, pages="314--325"} @article{beasley:orlib, author="J. E. Beasley", title="{OR}-Library: Distributing Test Problems by Electronic Mail", journal="Journal of the Operational Research Society", year=1990, volume=41, number=11, pages="1069--1072"} @article{beasley:scp, author="J. E. Beasley", title="An Algorithm for Set Covering Problems", journal=europs, year=1987, volume=31, pages="85--93"} @article{BH:scp, author="E. Balas and A. Ho", title="Set Covering Algorithms Using Cutting Planes, Heuristics, and Subgradient Optimisation: A Computational Study", journal=mathprogstud, year=1980, volume=12, pages="37--60"} @article{CB:capwarehouse, author="N. Christofides and J. E. Beasley", title="Extensions to a Lagrangean relaxation approach for the capacitated wharehouse location problem", journal=europs, volume=12, year=1983, pages="19--28"} @article{AK:capwarehouse, author="Umit Akinc and Basheer M. Khumawala", title="An Efficient Branch and Bound Algorithm for the Capacitated Warehouse Location Problem", journal=mgmtsci, year=1977, month=feb, volume=23, number=6, pages="585--594"} @article{Dakin:bandb, Author="R. Dakin", Title="A Tree Search Algorithm for Mixed Integer Programming Problems", Journal="Computer Journal", Volume=8, pages="250--255", year=1965} @article{Driebeck:penalties, Author="N. J. Driebeck", Title="An Algorithm for the Solution of Mixed Integer Programming Problems", journal=mgmtsci, volume=12, year=1966, pages="576--587" } @article{Erlenk:dualascent, Author="Donald Erlenklotter", Title="A Dual-Based Procedure for Uncapacitated Facility Location", journal=opsres, volume=26, number=6, year=1978, pages="993-1009" } @article{FS:duality, Author="Marshall L. Fisher and Jeremy F. Shapiro", Title="Constructive Duality in Integer Programming", journal=siamjappl, volume=27, number=1, year=1974, month=jul, pages="31--52" } @article{FT:addbound, Author="Matteo Fischetti and Paolo Toth", Title="An Additive Bounding Procedure for Combinatorial Optimization Problems", journal=opsres, year=1989, volume=37, number=2, pages="319--328" } @article{Fisher:lagrange, Author="Marshall L. Fisher", Title="The Lagrangian Relaxation Method for Solving Integer Programming Problems", journal=mgmtsci, year=1981, volume=27, number=1, month=jan, pages="1--18" } @article{Fisher:sched, Author="Marshall L. Fisher", Title="Optimal Solution of Scheduling Problems: Part {I}", journal=opsres, volume=21, year=1973, pages="1114-1127" } @article{Fisher:onemach, Author="Marshall L. Fisher", Title="A Dual Algorithm for the One-Machine Scheduling Problem", journal=mathprog, volume=11, year=1976, pages="229--251" } @article{FJV:mult, Author="Marshall L. Fisher and R. Jaikumar and Luk N. Van Wassenhove", Title="A Multiplier Adjustment Method for the Generalized Assignment Problem", journal=mgmtsci, year=1986, month=sep, number=9, volume=32, pages="1095--1103" } @article{Geoff:enum, Author="A.M. Geoffrion", Title="An Improved Implicit Enumeration Approach for Integer Programming", journal=opsres, volume=17, year=1969, pages="437--454" } @article{Geoff:lagrange, Author="A.M. Geoffrion", Title="Lagrangian Relaxation for Integer Programming", journal=mathprogstud, year=1974, volume=2, pages="82--114" } @article{GM:capfac, Author="A. M. Geoffrion and R. McBride", Title="Lagrangian Relaxation Applied to Capactitated Facility Location Problems", Journal=aiietrans, Year=1978, Volume=10, number=1, pages="40--47", month=mar } @article{GM:framework, Author="A. M. Geoffrion and R. E. Marsten", Title="Integer Programming Algorithms: A Framework and State-of-the-Art Survey", journal=mgmtsci, volume=18, year=1972, pages="465-491" } @article{Goffin:subgrad, Author="J. L. Goffin", Title="On the Convergence Rates of Subgradient Optimization Methods", journal=mathprog, volume=13, year=1977, pages="329--347" } @article{GR:gap, Author="Monique Guignard and Moshe B. Rosenwein", Title="An Improved Dual-Based Algorithm for the Generalized Assignment Problem", journal=opsres, year=1989, volume=37, number=4, pages="658--663" } @article{HK:TSP1, Author="Michael Held and Richard M. Karp", Title="The Travelling Salesman Problem and Minimum Spanning Trees", Journal=opsres, Year=1970, volume=18, pages="1138--1162" } @article{HK:TSP2, Author="Michael Held and Richard M. Karp", Title="The Travelling Salesman Problem and Minimum Spanning Trees: Part {II}", Journal=mathprog, Year=1971, volume=1, number=1, pages="6--25" } @article{HWC:subgrad, Author="Michael Held and Philip Wolfe and Harlan P. Crowder", Title="Validation of Subgradient Optimization", journal=mathprog, volume=6, number=1, year=1974, pages="62-88" } @article{KH:warehouse, Author="A. A. Kuehn and M. J. Hamburger", title="A Heuristic Program for Locating Warehouses", journal=mgmtsci, volume="9", number="9", year="1963", month=jul, pages="643--666"} @article{KP:splp, Author="Jakob Krarup and Peter Mark Pruzan", Title="The Simple Plant Location Problem: Survey and Synthesis", journal=europs, year=1983, number=1, pages="36--81", volume=12 } @incollection{LP:intprog, Author="Land, A. and Powell, S.", Title="Computer Codes for Problems of Integer Programming", Booktitle="Discrete Optimization II", year="1979", publisher="North Holland", address="New York", series="Annals of Discrete Mathematics", editor="P. L. Hammer and E. J. Johnson and B. H. Korte"} @article{LD:bandb, Author="A. Land and A. Doig", Title="An Automatic Method of Solving Discrete Programming Problems", Journal="Econometrika", volume=28, number=3, pages="497--520", year=1960} @article{MW:netdesign, Author="T.L. Magnanti and R. T. Wong", Title="Network Design and Transportation Planning: Models and Algorithms", journal= "Transportation Science", year=1984, month=feb, volume=18, number=1, pages="1-55" } @article{FHT:umpire, Author="J. J. H. Forest and J. P. H. Hirst and J. A. Tomlin", Title="Practical Solution of Large Mixed Integer Programming Problems with {U}mpire", journal= mgmtsci, year=1974, month=jan, volume=20, number=5, pages="736--773" } @article{Nemhauser:SPlagrange, Author="George L. Nemhauser and Glenn M. Weber", Title="Optimal Set Partitioning, Matchings and Lagrangian Duality", Year=1979, volume=26, pages="553-563", journal="Naval Research Logistics Quarterly" } @article{BJNSV:formulate, Author="Cynthia Barnhart and Ellis L. Johnson and George L. Nemhauser and Gabriele Sigismondi and Pamela Vance", Title="Formulating a Mixed Integer Programming Problem to Improve Solvability", Year=1993, volume=41, number=6, pages="1013--1019", journal="Operations Research" } @article{PR:bandc, Author="Manfred Padberg and Giovanni Rinaldi", Title="A Branch--and--Cut Algorithm for the Resolution of Large--Scale Symmetric Travelling Salesman Problems", journal="SIAM Review", year=1991, volume=33, pages="60--100", number=1} @article{Reinelt:tsplib, Author="Gerhard Reinelt", Title="{TSPLIB}--- A Traveling Salesman Problem Library", Journal="ORSA Journal on Computing", volume=3, number=4, year=1991, pages="376--384"} @article{AJ:tabu01, Author="Ronny Aboudi and Kurth J{\"{o}}rsten", journal="ORSA Journal on Computing", volume="6", number="1", year="1994", pages="82--93"} @article{Glover:tabuI, author="Fred Glover", title="Tabu Search-- Part {I}", journal="ORSA Journal on Computing", volume=1, number=3, pages="190--206", year=1989} @article{Glover:tabuII, author="Fred Glover", title="Tabu Search-- Part {II}", journal="ORSA Journal on Computing", volume=2, number=1, pages="4--32", year=1990} @article{Glover:tutorial, author="Fred Glover", title="Tabu Search: A Tutorial", journal="Interfaces", volume=20, number=4, pages="74--94", year=1990} @article{AD:lessons, Author="R. W. Ashford and R. C. Daniel", Title="Some Lessons in Solving Practical Integer Programs", Year=1992, volume=43, number=5, pages="425--433", journal="Journal of the Operational Research Society" } @article{Babai:hard, Author="L{\'{a}}szl{\'{o}} Babai", Title="Combinatorial Optimization is Hard", Year=1992, volume=12, number=5, month="September", pages="3--18", journal="Focus"} } @article{Johnson:tale, Author="David S. Johnson", Title="The {NP}-Completeness Column: An Ongoing Guide", Year=1992, volume=13, number=3, month="September", pages="502--524", journal="Journal of Algorithms"} } @book{OLR:biblio, Author="M. O'hEigeartaigh and J. K. Lenstra and A. H. G. Rinnooy Kan", Title="Combinatorial Optimization: Annotated Bibliographies", Publisher="Wiley", address="New York", year=1985} @book{AMO:flows, Author="Ravindra K. Ahuja and Thomas L. Magnanti and James B. Orlin", Title="Network Flows : Theory, Algorithms, and Applications", publisher="Prentice Hall", address="Englewood Cliffs, NJ", year="1993"} @book{Bertsekas:flows, Author="Dimitri P. Bertsekas", Title="Linear Network Optimization: Algorithms and Codes", publisher="{MIT} Press", address="Cambridge, MA", year="1991", annotate=""} @book{Hu:algorithms, Author="T. C. Hu", Title="Combinatorial Algorithms", publisher="Addison-Wesley", address="Reading, MA", year="1982", annotate=""} @book{Oxley:matroids, Author="J. G. Oxley", Title="Matroid Theory", publisher="Oxford University Press", year="1992", address="New York"} @book{PR:discopt, Author="R. Gary Parker and Ronald L. Rardin", Title="Discrete Optimization", Year=1988, address="Boston", Publisher="Academic Press", annotate="This textbook covers computational complexity, matroids, cutting plane technqiues, branch and bound, duality in integer programming, and approximation schemes. The coverage of heuristics is limited."} @book{AK:anneal, author="Emile H.L. Aarts and Jan Korst", title="Simulated Annealing and Boltzmann Machines: A Stochastic Approach to Combinatorial Optimization and Neural Computing", publisher="Wiley", address="Chichester", year=1989} @book{AVL:simulated, Author="Emile H. L. Aarts and Peter J. M. Van Laarhoven", Title="Simulated Annealing: Theory and Applications", Year=1987, Publisher="Kluwer Academic Publishers", annotate=""} @book{Sch:theory, Author="Alexander Schrijver", Title="Theory of Linear and Integer Programming", Year=1987, address="New York", Publisher="John Wiley and Sons", annotate="This textbook covers the theory of integer programming, especially polyhedral theory, computational complexity, and the theory of lattices."} @book{SM:foundations, Author="Harvey M. Salkin and Kamlesh Mathur", Title="Foundations of Integer Programming", Year=1989, address="New York", Publisher="North-Holland", annotate="Although this book was published in 1989, the majority of the references are from the 1960's and 1970's. The coverage of cutting plane methods does not include any of the recent work based on facet defining inequalities. The book does have reasonably good coverage of branch and bound and group theoretic techniques."} @book{Goldberg:genetic, Author="David E. Goldberg", Title="Genetic Algorithms in Search, Optimization, and Machine Learning", Year=1989, address="Reading, MA", Publisher="Addison--Wesley", annotate="This textbook is an easy to read introduction to Genetic algorithms, which can be used as heuristics for combinatorial optimization problems."} @book{Stoer:design, Author="Mechthild Stoer", Title="Design of Survivable Networks", Year=1992, address="Heidelberg", series="Lecture Notes in Mathematics", volume="1531", Publisher="Springer Verlag", annotate="This monograph describes a modern cutting plane approach to designing telecommunications networks that can survive the loss of links and nodes. A good example of modern cutting plane methods at work."} @book{Junger:asp, Author="Michael Junger", Title="Polyhedral Combinatorics and the Acyclic Subdigraph Problem", Year=1985, address="Berlin", Publisher="Helderman Verlag", annotate=""} @book{HS:algorithms, Author="Ellis Horowitz and Sartaj Sahni", Title="Fundamentals of Computer Algorithms", Year=1984, address="Rockville, MD", Publisher="Computer Science Press", annotate="There are lots of textbooks on algorithms. This one is distinguished by chapters on dynamic programming, branch and bound, and computational complexity."} @book{CLR:algorithms, Author="Thomas H. Cormen and Charles E. Leiserson and Ronald L. Rivest", Title="Introduction to Algorithms", Year=1990, address="Cambridge, MA", Publisher="MIT Press"} @book{Tarjan:algorithms, Author="Robert Endre Tarjan", Title="Data Structures and Network Algorithms", Year=1983, address="Philadelphia, PA", Publisher="SIAM"} @book{Coffman:scheduling, Author="E. G. Coffman", Title="Computer and Job Shop Scheduling Theory", publisher="Wiley", year="1976", address="New York"} @book{Blaz:scheduling, Author="Jacek Blazewicz", Title="Scheduling in computer and manufacturing systems", publisher="Springer-Verlag", year=1993, address="New York"} @book{NW:icopt, Author="George L. Nemhauser and Laurence A. Wolsey", Title="Integer and Combinatorial Optimization", Year=1988, address="New York", Publisher="John Wiley and Sons", annotate="This is an advanced graduate level text/reference book. It covers a wide range of topics, including linear programming, network flow problems, polyhedral theory, cutting plane methods, branch and bound methods, duality in integer programming, and computational complexity. The book may be a bit to advanced for the beginning student, but it is a very good book for the more advanced reader. The only weaknesses are in their area of heuristics- The coverage of simulated annealing, genetic algorithms and tabu search is limited or nonexistant."} AUTHOR Glover, Fred, Dr. TITLE Network models in optimization and their applications in practice. ADD AUTHOR Klingman, D. (Darwin) Phillips, Nancy V. PUBLISHER New York : Wiley, c1992. @book{GKP:flows, Author="Fred Glover and Darwin Klingman and Nancy Phillips", Title="Network Models in Optimization and Their Applications in Practice", publisher="Wiley", year="1992", address="New York"} @book{Williams:models, Author="H. P. Williams", Title="Model Building in Mathematical Programming", publisher="Wiley", year="1985", edition="Second", address="New York"} @book{GLS:geometric, author="Martin Gr{\"{o}}tschel and L{\'{a}}szl{\'{o}} Lov{\'{a}}sz and Alexander Schrijver", title="Geometric Algorithms and Combinatorial Optimization", publisher="Springer-Verlag", address="New York", year="1988"} @book{KLS:greedoids, author="Bernhard Korte and L{\'{a}}szl{\'{o}} Lov{\'{a}}sz and Rainer Schrader", title="Greedoids", publisher="Springer-Verlag", year="1991", address="New York"} @book{Lawler:combopt, Author="Eugene Lawler", Title="Combinatorial Optimization: Networks and Matroids", Year=1976, address="Fort Worth", Publisher="Saunders College Publishing", annotate="This is a very well written treatment of network flows and matroids. Unfortunately, it predates the theory of computational complexity. This book is now out of print. "} @book{Lawler:tour, Author="Eugene Lawler", Title="The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization", Year=1985, address="New York", Publisher="Wiley", annotate="This book discusses the traveling salesman problem from a number of points of view. Along the way, it discusses branch and bound, cutting plane, and heuristic approaches, along with computational complexity."} @book{Davis:handbook, Author="Lawrence Davis", Title="Handbook of Genetic Algorithms", year="1991", publisher="Van Nostrand Reinhold", address="New York", annotate="Just what it says-- A handbook on genetic algorithms."} @book{Davis:genandsim, Author="Lawrence Davis", Title="Genetic Algorithms and Simulated Annealing", year="1987", publisher="Morgan Kaufmann", address="Los Altos, CA"} @book{Reeves:modern, Author="Colin R. Reeves", Title="Modern Heuristic Techniques for Combinatorial Problems", year="1993", publisher="Halsted Press", address="New York", annotate="A collection of papers on heuristic technqiues, including simulated annealing and tabu search."} @book{Dreyfus:art, Author="Stuart E. Dreyfus and Averill M. Law", Title="The Art and Theory of Dynamic Programming", year="1977", publisher="Halsted Press", address="New York"} @book{MT:knapsack, Author="Silvano Martello and Paolo Toth", title="Knapsack Problems: Algorithms and Computer Implementations", publisher="Wiley", address="New York", year="1990", annotate="Covers branch and bound and dynamic programming approaches to knapsack problems. Includes Fortran codes."} BY: Martello, Silvano. Toth, Paolo. TITLE: Knapsack problems : algorithms and computer implementations TITLE-NOTE: Silvano Martello and Paolo Toth. PUBLISHED: Chichester ; New York : J. Wiley & Sons, c1990. SUBJECT: Computational complexity. @book{GJ:candi, Author="Michael R. Garey and David S. Johnson", Title="Computers and Intractibility: A Guide to the Theory of {NP}-Completeness", Year=1979, address="New York", Publisher="W. H. Freeman and Company", annotate="This book covers that theory of computational complexity. It also includes a large list of known NP-complete and NP-hard problems."} @book{Foulds:combopt, Author="L. R. Foulds", Title="Combinatorial Optimization for Undergraduates", Year=1984, address="New York", Publisher="Springer Verlag", annotate="This book covers a variety of topics including linear and integer programming, dynamic programming, and network flows. The book conlcudes with a chapter on applications."} @book{PS:combopt, Author="Christos H. Papadimtriou and Kenneth Steiglitz", Title="Combinatorial Optimization: Algorithms and Complexity", Year=1982, address="Englewood Cliffs, NJ", Publisher="Prentice-Hall", annotate="This textbook covers computational complexity, linear programming and the simplex method, network flows, matching problems, matriods, integer programming, cutting plane algorithms, branch and bound algorithms, dynamic programming, heuristics, and approximation algorithms. The material on cutting planes, approximation algorithms and heuristics is somewhat out of date, but overall, this is a very useful textbook. Unfortunately, the book is out of print."} @book{Papa:complexity, Author="Christos H. Papadimtriou", Title="Computational Complexity", Year=1994, address="Reading, MA", Publisher="Addison-Wesley", annotate=""} @article{Shapiro:lagrange, Author="Jeremy F. Shapiro", Title="A Survey of Lagrangian Techniques for Discrete Optimization", journal=andiscrete, year=1979, volume=5, pages="113--138" } @article{Tomlin:penalties, Author="J.A. Tomlin", Title="An improved branch and bound method for integer programming", journal=opsres, volume=19, year=1971, pages="1070--1075" } @article{Wong:steiner, Author="Richard T. Wong", Title="A Dual Ascent Approach for Steiner Tree Problems on a Directed Graph", journal=mathprog, volume=28, number=unknown, year=1984, pages="271-287" } @article{Lin:tsp, Author="Lin, S.", Title="Computer Solutions of the Traveling Salesman Problem", journal=bstj, volume=44, year=1965, pages="2245-2269"} @article{sa:haje88a, Author="Bruce Hajek", Title="Cooling Schedules for Optimal Annealing", journal=mathor, year=1988, volume=13, pages="311-329"}