15-853: Algorithms in the Real World (Guy Blelloch)

#

Topic 4: Integer Programming

[ Topics |
Scribe Notes |
Readings |
Text Books |
Links ]

Integer Programming 1 (draft) (Andrew Begel)
Integer Programming 2 (draft) (Stephen Chenney)
These readings will be/have been given out in class.
Ignizio and Cavalier.
Linear programming.
**Chapter 11** (Integer Programming)

This chapter both has an introduction to the various application areas
of integer and mixed-integer programming and an
introduction solution techniques
including Branch-and-bound and cutting plane techniques.
G. L. Nemhauser. The age of optimization: solving
large-scale real-world problems. (abstract).

This paper has
some overlap with the paper "Recent developments and future directions
in mathematical programming" from linear programming but concentrates
on applications.
**I took this off the list -- you do not need to read it**
R. Subramanian, R. P. Scheff, Jr., J. D. Quillinan, D. S. Wiper, and R. E.
Marsten.
Coldstart: Fleet assignment at Delta Air Lines.
(abstract).

The paper states that Delta saves $300 Million a year by using
mixed-integer programming to schedule their fleet.
George L. Nemhauser and Laurence A. Wolsey.
Integer and combinatorial optimization.
Wiley, 1988.
H. M Salkin and K. Mathur.
Foundations of Integer Programming.
North-Holland, 1989.
Stavros A. Zenios (ed.).
Financial optimization.
Cambridge University Press, 1993.
Dimitris Bertsimas and John N. Tsitsiklis.
Introduction to Linear Optimization.
Athena Scientific, 1997
G. L. Nemhauser, A.H.G. Rinnooy Kan, and M. J. Todd (ed.).
Optimization.
Elsevier, 1989.

See the list under linear programming.
There is enough overlap that it is not worth repeating the list.

Back to the Algorithms in the Real World home page.

Guy Blelloch,
guyb@cs.cmu.edu.