everything.study
6.859

Integer Programming and Combinatorial Optimization

Graduate · Historical course

Fall 2009

The course is a comprehensive introduction to the theory, algorithms and applications of integer optimization and is organized in four parts: formulations and relaxations, algebra and geometry of integer optimization, algorithms for integer optimization, and extensions of integer optimization.

Readings

  • Chapter assignments are from the course textbook: Bertsimas, Dimitris, and Robert Weismantel. Optimization over Integers . Belmont, MA: Dynamic Ideas, 2005. ISBN: 9780975914625.
    Listed reading
  • LEC #: 1 · TOPICS: Formulations · READINGS: Chapter 1
    Reading assignment
  • LEC #: 2 · TOPICS: Complexity · READINGS: Appendix B
    Reading assignment
  • LEC #: 3 · TOPICS: Methods to enhance formulations I · READINGS: Appendix A; Chapter 2
    Reading assignment
  • LEC #: 4 · TOPICS: Methods to enhance formulations II · READINGS: Chapter 2
    Reading assignment
  • LEC #: 5-7 · TOPICS: Ideal formulations · READINGS: Chapter 3
    Reading assignment
  • LEC #: 8-9 · TOPICS: Duality theory · READINGS: Chapter 4
    Reading assignment
  • LEC #: 10 · TOPICS: Algorithms for solving relaxations · READINGS: Chapter 5
    Reading assignment
  • LEC #: 11 · TOPICS: Robust discrete optimization · READINGS: Chapter 14
    Reading assignment
  • LEC #: 12-13 · TOPICS: Lattices · READINGS: Chapter 6
    Reading assignment
  • LEC #: 14-15 · TOPICS: Algebraic geometry · READINGS: Chapter 7
    Reading assignment
  • LEC #: 16 · TOPICS: Geometry · READINGS: Chapter 8
    Reading assignment
  • LEC #: 17-18 · TOPICS: Cutting plane methods · READINGS: Chapter 9
    Reading assignment
  • LEC #: 19 · TOPICS: Enumerative methods · READINGS: Chapter 11
    Reading assignment
  • LEC #: 20 · TOPICS: Heuristic methods · READINGS: Chapter 11
    Reading assignment
  • LEC #: 21-23 · TOPICS: Approximation algorithms · READINGS: Chapter 12
    Reading assignment
  • LEC #: 24-25 · TOPICS: Mixed integer optimization · READINGS: Chapter 13
    Reading assignment
  • Bertsimas, Dimitris, and Robert Weismantel. Optimization over Integers . Belmont, MA: Dynamic Ideas, 2005. ISBN: 9780975914625.
    Required
Sources