A Reading List in Combinatorial Optimization ^{∗}

Brian Borchers

April 21, 1994

This document is a bibliography of books and survey articles on various topics in combinatorial optimization and integer programming. I’ve tried to limit this bibliography primarily to books and survey papers, because there are far more research papers on each of these topics than I could ever hope to include in this bibliography. Hopefully, the papers and books that I have included will point the reader to important research papers in each topic.

This bibliography can be obtained via gopher or anonymous ftp from the Mathematics Archives at archives.math.utk.edu. I’d like to expand and improve on this bibliography– If you have any entries or additional areas that you’d like to see included in the bibliography, please send your comments to me (borchers@nmt.edu).

Textbooks that cover a broad range of topics in combinatorial optimization include [Fou84, Law76, NW88, PR88, PS82, SM89, Sch87]. The book by Papadimitriou and Steiglitz is a good choice for a first course in combinatorial optimization. Unfortunately, it is currently out of print. The book by Nemhauser and Wolsey is a good choice for more advanced students, but I wouldn’t use it for a first course in combinatorial optimization. I also like the book by Parker and Rardin, but its coverage of some topics is limited.

Computational Complexity theory plays an important role in combinatorial optimization, separating the easy problems that can be solved in polynomial time from the hard (particularly “NP-Hard”) problems for which no polynomial time algorithms are known. Books on this topic include [GJ79, Pap94].

The first combinatorial optimization problems to be extensively studied were problems on graphs, including the shortest path problem, max flow problems, and matching. Books on this topic include [AMO93, Ber91, GKP92, Law76].

Many combinatorial optimization problems can be formulated as integer programming problems. In formulating an integer programming problem, there are many tricks that can be used to make the problem easier to solve. Books and articles on the formulation of integer programming and mixed integer programming problems include [AD92, BJN^{+}93, Wil85].

∗\begin{matrix}c \\ ◯ \end{matrix}1994 by Brian Borchers. This article may be freely duplicated and distributed so long as no consideration is received in return, and this copyright notice remains intact.

Branch and bound algorithms are commonly used to solve integer programming problems. Branch and bound algorithms are discussed in nearly all of the textbooks described above, including [NW88, PR88, PS82, SM89]. Branch and bound and dynamic programming algorithms for the knapsack problem are discussed in [MT90].

Cutting plane algorithms are another approach to integer programming problems. These are described in [NW88, PR88, PS82, SM89]. Early cutting plane algorithms such as Gomory’s cutting plane algorithm have not proven to be very effective. However, recent work in problem specific cutting plane algorithms and algorithms that combine branch and bound with cutting planes has been somewhat more successful. Some recent examples of cutting plane techniques include [Jun85, Law85, PR91, Sto92]. Some theoretical material on cutting planes can be found in [GLS88, Sch87].

Heuristics for combinatorial optimization problems are algorithms that find “good” solutions without any guarantee that the solutions are optimal. In recent years, there has been a lot of interest in heuristics, including genetic algorithms [Dav87, Dav91, Gol89], simulated annealing [AK89, AL87, Dav87, Ree93], and tabu search [Glo90b, Glo89, Glo90a, Ree93].

Approximation schemes are algorithms that are guaranteed to produce a solution that is within ϵ of optimality. Of particular interest are polynomial time approximation schemes- algorithms that given ϵ find an answer within a factor ϵ of optimality while running in polynomial time. Some approximation schemes for NP-hard problems are discussed in [PS82, PR88, HS84]. Unfortunately, there are also many NP-hard problems for which such approximation schemes are impossible unless P=NP. Some negative results are discussed in [PS82, PR88]. Very recently, work on transparent proofs has resulted in a large number of theorems about the non existence of polynomial time approximation schemes for various problems. These are discussed briefly in [Bab92, Joh92].

Algorithms and data structures are particularly important in implementing techniques for combinatorial optimization. Backtracking and dynamic programming are among the important algorithmic issues. Good implementations of data structures such as priority queues are important in getting good performance from the algorithms. Books that discuss these issues include [CLR90, HS84, Hu82, Tar83].

Scheduling problems are an important area of research in combinatorial optimization. Some books on this topic include [Bla93, Cof76, Hu82].

Matroids are a kind of algebraic structure within which some combinatorial optimization problems can easily be solved. Matroids are discussed in [Law76, Oxl92, NW88, PS82, PR88]. Greedoids, an extension of matroids, are described in [KLS91].

One interesting approach to integer programming problems is basis reduction. This is discussed in [GLS88, NW88, SM89, Sch87].

Duality in integer programming is another of research. This topic is discussed in [Fis81, NW88, PR88, Sha79].

There are a number of collection of test problems in combinatorial optimization that can be obtained via anonymous FTP. These include [Bea90, BBI92, Rei91].

Finally, a very useful, but slightly out of date annotated bibliography can be found in [OLK85].

References

[AD92] R. W. Ashford and R. C. Daniel. Some lessons in solving practical integer programs. Journal of the Operational Research Society, 43(5):425–433, 1992.

[AK89] Emile H.L. Aarts and Jan Korst. Simulated Annealing and Boltzmann Machines: A Stochastic Approach to Combinatorial Optimization and Neural Computing. Wiley, Chichester, 1989.

[AL87] Emile H. L. Aarts and Peter J. M. Van Laarhoven. Simulated Annealing: Theory and Applications. Kluwer Academic Publishers, 1987.

[AMO93] Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin. Network Flows : Theory, Algorithms, and Applications. Prentice Hall, Englewood Cliffs, NJ, 1993.

[Bab92] László Babai. Combinatorial optimization is hard. Focus, 12(5):3–18, September 1992.

[BBI92] Robert E. Bixby, E. Andrew Boyd, and Ronni R. Indovina. MIPLIB: A test set of mixed integer programming problems. SIAM News, 25(20):16, March 1992.

[Bea90] J. E. Beasley. OR-library: Distributing test problems by electronic mail. Journal of the Operational Research Society, 41(11):1069–1072, 1990.

[Ber91] Dimitri P. Bertsekas. Linear Network Optimization: Algorithms and Codes. MIT Press, Cambridge, MA, 1991.

[BJN^{+}93] Cynthia Barnhart, Ellis L. Johnson, George L. Nemhauser, Gabriele Sigismondi, and Pamela Vance. Formulating a mixed integer programming problem to improve solvability. Operations Research, 41(6):1013–1019, 1993.

[Bla93] Jacek Blazewicz. Scheduling in computer and manufacturing systems. Springer-Verlag, New York, 1993.

[CLR90] Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest. Introduction to Algorithms. MIT Press, Cambridge, MA, 1990.

[Cof76] E. G. Coffman. Computer and Job Shop Scheduling Theory. Wiley, New York, 1976.

[Dav87] Lawrence Davis. Genetic Algorithms and Simulated Annealing. Morgan Kaufmann, Los Altos, CA, 1987.

[Dav91] Lawrence Davis. Handbook of Genetic Algorithms. Van Nostrand Reinhold, New York, 1991.

[Fis81] Marshall L. Fisher. The lagrangian relaxation method for solving integer programming problems. Management Science, 27(1):1–18, January 1981.

[Fou84] L. R. Foulds. Combinatorial Optimization for Undergraduates. Springer Verlag, New York, 1984.

[GJ79] Michael R. Garey and David S. Johnson. Computers and Intractibility: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York, 1979.

[GKP92] Fred Glover, Darwin Klingman, and Nancy Phillips. Network Models in Optimization and Their Applications in Practice. Wiley, New York, 1992.

[Glo89] Fred Glover. Tabu search– part I. ORSA Journal on Computing, 1(3):190–206, 1989.

[Glo90a] Fred Glover. Tabu search– part II. ORSA Journal on Computing, 2(1):4–32, 1990.

[Glo90b] Fred Glover. Tabu search: A tutorial. Interfaces, 20(4):74–94, 1990.

[GLS88] Martin Grötschel, László Lovász, and Alexander Schrijver. Geometric Algorithms and Combinatorial Optimization. Springer-Verlag, New York, 1988.

[Gol89] David E. Goldberg. Genetic Algorithms in Search, Optimization, and Machine Learning. Addison–Wesley, Reading, MA, 1989.

[HS84] Ellis Horowitz and Sartaj Sahni. Fundamentals of Computer Algorithms. Computer Science Press, Rockville, MD, 1984.

[Hu82] T. C. Hu. Combinatorial Algorithms. Addison-Wesley, Reading, MA, 1982.

[Joh92] David S. Johnson. The NP-completeness column: An ongoing guide. Journal of Algorithms, 13(3):502–524, September 1992.

[Jun85] Michael Junger. Polyhedral Combinatorics and the Acyclic Subdigraph Problem. Helderman Verlag, Berlin, 1985.

[KLS91] Bernhard Korte, László Lovász, and Rainer Schrader. Greedoids. Springer-Verlag, New York, 1991.

[Law76] Eugene Lawler. Combinatorial Optimization: Networks and Matroids. Saunders College Publishing, Fort Worth, 1976.

[Law85] Eugene Lawler. The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. Wiley, New York, 1985.

[MT90] Silvano Martello and Paolo Toth. Knapsack Problems: Algorithms and Computer Implementations. Wiley, New York, 1990.

[NW88] George L. Nemhauser and Laurence A. Wolsey. Integer and Combinatorial Optimization. John Wiley and Sons, New York, 1988.

[OLK85] M. O’hEigeartaigh, J. K. Lenstra, and A. H. G. Rinnooy Kan. Combinatorial Optimization: Annotated Bibliographies. Wiley, New York, 1985.

[Oxl92] J. G. Oxley. Matroid Theory. Oxford University Press, New York, 1992.

[Pap94] Christos H. Papadimtriou. Computational Complexity. Addison-Wesley, Reading, MA, 1994.

[PR88] R. Gary Parker and Ronald L. Rardin. Discrete Optimization. Academic Press, Boston, 1988.

[PR91] Manfred Padberg and Giovanni Rinaldi. A branch–and–cut algorithm for the resolution of large–scale symmetric travelling salesman problems. SIAM Review, 33(1):60–100, 1991.

[PS82] Christos H. Papadimtriou and Kenneth Steiglitz. Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, Englewood Cliffs, NJ, 1982.

[Ree93] Colin R. Reeves. Modern Heuristic Techniques for Combinatorial Problems. Halsted Press, New York, 1993.

[Rei91] Gerhard Reinelt. TSPLIB— a traveling salesman problem library. ORSA Journal on Computing, 3(4):376–384, 1991.

[Sch87] Alexander Schrijver. Theory of Linear and Integer Programming. John Wiley and Sons, New York, 1987.

[Sha79] Jeremy F. Shapiro. A survey of lagrangian techniques for discrete optimization. Annals of Discrete Mathematics, 5:113–138, 1979.

[SM89] Harvey M. Salkin and Kamlesh Mathur. Foundations of Integer Programming. North-Holland, New York, 1989.

[Sto92] Mechthild Stoer. Design of Survivable Networks, volume 1531 of Lecture Notes in Mathematics. Springer Verlag, Heidelberg, 1992.

[Tar83] Robert Endre Tarjan. Data Structures and Network Algorithms. SIAM, Philadelphia, PA, 1983.

[Wil85] H. P. Williams. Model Building in Mathematical Programming. Wiley, New York, second edition, 1985.