课程大纲

本课程对整数最优化的理论、算法和应用做了全面的介绍，共分为四部分：

第一部分：公式化和松弛，第1-8课

讨论如何将整数最优化问题公式化，如何增强公式以提高松弛的质量，如何获得理想公式、整数最优化的对偶性，以及如何在实际中和理论上解决因而发生的松弛。

第二部分：整数最优化的几何学和代数学，第9-14课

逐步阐明格论，概述影响整数最优化的代数几何学思想，并讨论整数最优化的几何学。这些课堂讲授为发展算法提供基础。

第三部分：整数最优化的算法，第15-22课

阐述割平面方法、整基方法、枚举和启发式方法和逼近算法。我们处理方法的主要特点是我们的算法是自然地从第二部分讨论的代数和几何发展的基础之上发展起来的。

第四部分：整数最优化的扩展，第23－25课

处理混合整数最优化和鲁棒离散最优化。这两个领域在实际应用中都有着非常重要的意义。因为现实世界通常都同时有连续和离散变量，并有着不确定的元素，这需要转换成易处理的模式。

讲师

Dimitris Bertsimas教授

所需教材

Bertsimas, Dimitris和Robert Weismantel.〈整数最优化〉 ，Belmont, Massachusetts: 《动态的观点》，December 2004. ISBN: 0975914626.这是这本书正式出版前的版本。

要求

评分表

项目	百分比
期末测验	30%
期中测验	30%
家庭作业	30%
课堂贡献 (课堂参与及书评)	10%

Course Outline

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

Grading Table

ACTIVITIES	PERCENTAGES
Final Exam	30%
Midterm Exam	30%
Homework	30%
Contributions to Class (Class participation and comments on book)	10%