everything.study
6.251

Introduction to Mathematical Programming

Graduate · Historical course

Fall 2009

This course is an introduction to linear optimization and its extensions emphasizing the underlying mathematical structures, geometrical ideas, algorithms and solutions of practical problems. The topics covered include: formulations, the geometry of linear optimization, duality theory, the simplex method, sensitivity analysis, robust optimization, large scale optimization network flows, solving problems with an exponential number of constraints and the ellipsoid method, interior point methods, semidefinite optimization, solving real world problems problems with computer software, discrete optimization formulations and algorithms.

Readings

  • Chapter assignments are from the required textbook: Bertsimas, Dimitris, and John Tsitsiklis. Introduction to Linear Optimization . Belmont, MA: Athena Scientific, 1997. ISBN: 9781886529199.
    Listed reading
  • LEC #: 1 · TOPICS: Formulations · READINGS: Chapter 1
    Reading assignment
  • LEC #: 2 · TOPICS: Geometry I · READINGS: Chapter 2.1-2.3
    Reading assignment
  • LEC #: 3 · TOPICS: Geometry II · READINGS: Chapter 2.4-2.6
    Reading assignment
  • LEC #: 4 · TOPICS: Geometry III · READINGS: Chapter 2.7-2.9
    Reading assignment
  • LEC #: 5 · TOPICS: Simplex method I · READINGS: Chapter 3.1-3.2
    Reading assignment
  • LEC #: 6 · TOPICS: Simplex method II · READINGS: Chapter 3.3-3.4
    Reading assignment
  • LEC #: 7 · TOPICS: Simplex method III · READINGS: Chapter 3.5
    Reading assignment
  • LEC #: 8 · TOPICS: Simplex method IV · READINGS: Chapter 3.6-3.8
    Reading assignment
  • LEC #: 9 · TOPICS: Duality theory I · READINGS: Chapter 4.1-4.4
    Reading assignment
  • LEC #: 10 · TOPICS: Duality theory II · READINGS: Chapter 4.5
    Reading assignment
  • LEC #: 11 · TOPICS: Duality theory III · READINGS: Chapter 4.6-4.11
    Reading assignment
  • LEC #: 12 · TOPICS: Sensitivity analysis · READINGS: Chapter 5.1-5.7
    Reading assignment
  • LEC #: 14 · TOPICS: Large scale optimization I · READINGS: Chapter 6.1-6.4
    Reading assignment
  • LEC #: 15 · TOPICS: Large scale optimization II · READINGS: Chapter 6.5
    Reading assignment
  • LEC #: 16 · TOPICS: Network flows I · READINGS: Chapter 7.1-7.2
    Reading assignment
  • LEC #: 17 · TOPICS: Network flows II · READINGS: Chapter 7.3-7.4
    Reading assignment
  • LEC #: 18 · TOPICS: The Ellipsoid method · READINGS: Chapter 8.1-8.4
    Reading assignment
  • LEC #: 19 · TOPICS: Problems with exponentially many constraints · READINGS: Chapter 8.5-8.6
    Reading assignment
  • LEC #: 20 · TOPICS: Interior point methods I · READINGS: Chapter 9.1-9.2
    Reading assignment
  • LEC #: 21 · TOPICS: Interior point methods II · READINGS: Chapter 9.3-9.5
    Reading assignment
  • LEC #: 23 · TOPICS: Semidefinite optimization · READINGS: Freund, Robert. “Introduction to Semidefinite Programming.” ( PDF ) (Used with permission.) ↗
    Reading assignment
  • LEC #: 24 · TOPICS: Discrete optimization I · READINGS: Chapter 10
    Reading assignment
  • LEC #: 25 · TOPICS: Discrete optimization II · READINGS: Chapter 11
    Reading assignment
Sources