56:272 Integer Programming & Network Flows Fall Semester 2003

Textbook

Wolsey, L. A. (1998). Integer Programming. New York, John Wiley & Sons.
A textbook for courses in integer/mathematical programming, which explains how to construct algorithms or use existing commercial software to obtain solutions for a variety of real-world problems such as airline timetables or production line schedules. Topics covered include improved modeling, cutting plain theory, heuristic methods, and branch-and-cut and integer programming decomposition algorithms.

This textbook has been ordered at IMU Bookstore. Also, a copy will be placed on reserve in the Engineering Library.

Lecture materials (in pdf format, either 1, 2, or 8 screens per page), together with the syllabus, homework assignments, sample exams, etc. are available to the students via this web site.

Reserve Book List

• Boffey, T. B. (1982). Graph Theory in Operations Research. London, Macmillan Press, Ltd.(out-of-print)
  For several years I used this as the primary textbook for the course. It covers network problems and some combinatorial optimization, but lacks coverage of integer programming models and algorithms.
  
• Chartrand, G. (1977). Introductory Graph Theory. New York, Dover.
  Author Gary Chartrand covers the important elementary topics of graph theory and its applications. In addition, he presents a large variety of proofs designed to strengthen mathematical techniques and offers challenging opportunities to have fun with mathematics. Previously published as Graphs as Mathematical Models. This Dover edition is bargain-priced at only $8.95.
  
• Daskin, M. (1995). Network and Discrete Location Models, Algorithms, and Applications. New York, John Wiley and Sons, Inc.
  A book/disk guide to using and developing facility location models, for students and professionals, with an introduction to model-building methods and solution algorithms using classical location problems and real-life extensions of the basic models. The text outlines methodological tools for solving location models, and concentrates on covering models, center problems, median models, and fixed charge location problems. Appendices offer instructions and tables for using programs on the disk. (The programs may also be downloaded from the author's web page.)
  
• Martin, R. K. (1999). Large Scale Linear and Integer Optimization: A Unified Approach, Kluwer Academic Publishers.
  Parts I and II of Large Scale Linear and Integer Optimization provide an introduction to linear optimization using two simple but unifying ideas-projection and inverse projection. The ideas of projection and inverse projection are also extended to integer linear optimization. With the projection-inverse projection approach, theoretical results in integer linear optimization become much more analogous to their linear optimization counterparts. Hence, with an understanding of these two concepts, the reader is equipped to understand fundamental theorems in an intuitive way.
  Part III presents the most important algorithms that are used in commercial software for solving real-world problems. Part IV shows how to take advantage of the special structure in very large scale applications through decomposition. Part V describes how to take advantage of special structure by modifying and enhancing the algorithms developed in Part III. This section contains a discussion of the current research in linear and integer linear programming. The author also shows in Part V how to take different problem formulations and appropriately `modify' them so that the algorithms from Part III are more efficient. Again, the projection and inverse projection concepts are used in Part V to present the current research in linear and integer linear optimization in a very unified way.
  
• Plane, D. R. and C. McMillan, Jr. (1971). Discrete Optimization: Integer Programming & Network Analysis for Management Decisions. Englewood Cliffs, NJ, Prentice-Hall.
  A comprehensive volume that assumes little or no prior mathematical programming experience; Coverage includes chapters devoted to mgmt science and mathematical programming, problem formulation for zero-one programming, solving zero-one problems via implicit enumeration, integer linear programming, special applications of integer programming, network optimization, & an integer programming case study.
  
  

The above books will be put on reserve in the Engineering Library.

Other References

• Bertsekas, D. P. (1998). Network Optimization: Continuous and Discrete Models. Belmont, Massachusetts, Athena Scientific.
  An introductory, yet comprehensive and up-to-date treatment of linear, nonlinear, and discrete network optimization problems, their applications, and their analytical and algorithmic methodology. It covers extensively theory, algorithms, and applications, and it aims to bridge the gap between linear and nonlinear network optimization on one hand, and integer/combinatorial network optimization on the other.
  
• Brown, J. A., S. Pakin, et al. (1988). APL2 at a Glance. Englewood Cliffs, NJ, Prentice-Hall.
  APL Level II is a computer language which is well-suited for implementing mathematical programming algorithms.
  
• Diestel, R. (2000). Graph Theory. New York, Springer-Verlag. An on-line edition of this textbook is available at the URL:
  http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/
  
• Lawler, E. L., J. K. Lenstra, et al., Eds. (1985). The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. Chichester, John Wiley & Sons.
  Provides an in-depth treatment of the Traveling Salesman problem--the archetypical problem in combinatorial optimization. Each chapter deals with a different aspect of the problem, and has been written by an acknowledged expert in the field. Focusses on the essential ideas in a self-contained manner. Includes exercises and an extensive bibliography.
  
• Winston, W. L. (1997). Operations Research: Applications and Algorithms (3rd edition) Boston, PWS-Kent Publishing Company.
  A very complete coverage of linear and integer programming, network models, dynamic programming, etc.
  

 
to IP&NF home page.

http://asrl.ecn.uiowa.edu/dbricker/ipnf_text_refs.html
dennis-bricker@uiowa.edu

Last modified: 23 August 2003