Integer programming and combinatorial optimization

Lectures: 2 sessions / week, 1.5 hours / session

Recitations: 1 session / week, 1 hour / session

The course is a comprehensive introduction to the theory, algorithms and applications of integer optimization and is organized in five parts.

Discusses how to formulate integer optimization problems, how to enhance the formulations to improve the quality of relaxations, how to obtain ideal formulations, the duality of integer optimization and how to solve the resulting relaxations both practically and theoretically. It also gives insight on why integer optimization problems are difficult.

Treats robust discrete optimization. This is a tractable methodology to address problems under uncertainty.

Develops the theory of lattices, outlines ideas from algebraic geometry that have had an impact on integer optimization, and discusses the geometry of integer optimization. These lectures provide the building blocks for developing algorithms.

Develops cutting plane methods, enumerative and heuristic methods and approximation algorithms.

Treats mixed integer optimization. This is a practically significant area as real world problems have very often both continuous and discrete variables.

Bertsimas, Dimitris, and Robert Weismantel. Optimization over Integers. Belmont, MA: Dynamic Ideas, 2005. ISBN: 9780975914625.

Grades will be determined by performance on the following requirements. Weights are approximate, and class participation is an important tie breaker.

Don't show me this again

This is one of over 2,200 courses on OCW. Find materials for this course in the pages linked along the left.

MIT OpenCourseWare is a free & open publication of material from thousands of MIT courses, covering the entire MIT curriculum.

No enrollment or registration. Freely browse and use OCW materials at your own pace. There's no signup, and no start or end dates.

Knowledge is your reward. Use OCW to guide your own life-long learning, or to teach others. We don't offer credit or certification for using OCW.

Made for sharing. Download files for later. Send to friends and colleagues. Modify, remix, and reuse (just remember to cite OCW as the source.)

Learn more at Get Started with MIT OpenCourseWare