15.083 整数规划与组合优化

MIT Course 15 · Operations Research/Statistics · 课号 15.083

TL;DR

• NP 难离散优化问题的精确与近似求解，聚焦多面体组合学与有效不等式。
• Chvátal-Gomory 割平面、Benders 分解与列生成（Column generation）技术大幅提升求解边界。
• 完全单模矩阵（Totally unimodular）性质建立了整数规划与线性松弛完全等价的充分条件。

课程简介 / Description

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.

讲义 / Lecture Notes

• 1
  • Formulations
  • (PDF)
• 2
  • Complexity
  • (PDF)
• 3
  • Methods to enhance formulations I
  • (PDF)
• 4
  • Methods to enhance formulations II
  • (PDF)
• 5
  • Ideal formulations I
  • (PDF)
• 6
  • Ideal formulations II
  • (PDF)
• 7
  • Ideal formulations III
  • (PDF)
• 8
  • Duality theory I
  • (PDF)
• 9
  • Duality theory II
  • (PDF)
• 10
  • Algorithms for solving relaxations
  • (PDF)
• 11
  • Robust discrete optimization
  • (PDF)
• 12
  • Lattices I
  • (PDF)
• 13
  • Lattices II
  • (PDF)
• 14
  • Algebraic geometry I
  • (PDF)
• 15
  • Algebraic geometry II
  • (PDF)
• 16
  • Geometry
  • (PDF)
• 17
  • Cutting plane methods I
  • (PDF)
• 18
  • Cutting plane methods II
  • (PDF)
• 19
  • Enumerative methods
  • (PDF)
• 20
  • Heuristic methods
  • (PDF)
• 21
  • Approximation algorithsm I
  • (PDF)
• 22
  • Approximation algorithms II
  • (PDF)
• 23
  • Approximation algorithms III
  • (PDF)
• 24
  • Mixed integer optimization I
  • (PDF)
• 25
  • Mixed integer optimization II
  • (PDF)

本资料整理自 MIT OpenCourseWare，遵循 Creative Commons BY-NC-SA 4.0 许可协议，仅供个人学习使用。