everything.study
15.083

Integer Optimization

4-0-8 units · Graduate

In-depth treatment of mixed-integer optimization. Topics include modeling techniques, combinatorial optimization, ideal formulations, cutting plane methods, branching algorithms, row generation algorithms, column generation algorithms, heuristic algorithms, and mixed-integer non-linear optimization. Instruction provided in modeling complex problems arising in practice; understanding the theory of integer optimization; knowing the core technologies employed within modern solvers; and developing algorithms to solve large-scale problems for which off-the-shelf solvers may not be sufficient. Examples drawn from a broad range of industries, such as transportation, energy, telecommunications, finance, product design, sports, and social networks. Includes a term project.

Fall 2009 · Integer Programming and Combinatorial Optimization

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

Prerequisites & course information

Prereq: 6.7210[J] or 15.093 G (Spring) 4-0-8 units

Sources