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

# Topic 4: Integer Programming

### Topic Outline

• Uses of integer constraints
• Either-or constraints
• p out of n constraints
• boolean constraints (zero-one variables)
• piecewise linear functions
• Algorithms
• Linear programming approximations
• Branch and bound
• implicit enumeration
• cutting-plane methods
• Applications
• Knapsack and Traveling salesman problems
• Airline crew scheduling
• ### Scribe Notes

• 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.
• ### Recommended Text Books

• 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.