Courses:

When you click the Amazon logo to the left of any citation and purchase the book (or other media) from Amazon.com, MIT OpenCourseWare will receive up to 10% of this purchase and any other purchases you make during that visit. This will not increase the cost of your purchase. Links provided are to the US Amazon site, but you can also support OCW through Amazon sites in other regions. Learn more.

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

Part I: Formulations and Relaxations, Lectures 1-8

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.

Part II: Algebra and Geometry of Integer Optimization, Lectures 9-14

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.

Part III: Algorithms for Integer Optimization, Lectures 15-22

Develops cutting plane methods, integral basis methods, enumerative and heuristic methods and approximation algorithms. The key characteristic of our treatment is that our development of the algorithms is naturally based on the algebraic and geometric developments of Part II.

Part IV: Extensions of Integer Optimization, Lectures 23-25

Treats mixed integer optimization and robust discrete optimization. Both areas are practically significant as real world problems have very often both continuous and discrete variables and have elements of uncertainty that need to be addressed in a tractable manner.

Instructor

Professor Dimitris Bertsimas

Required Book

Bertsimas, Dimitris, and Robert Weismantel. Optimization over Integers. Belmont, Massachusetts: Dynamic Ideas, December 2004. ISBN: 0975914626. The book is the prepublication edition of the book.

Requirements