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

next up previous
Topic 4: Integer Programming

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

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)

    • Readings

    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.

    • Further Readings and Links

    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.