MyOOPS開放式課程
請加入會員以使用更多個人化功能
來自全球頂尖大學的開放式課程,現在由世界各國的數千名義工志工為您翻譯成中文。請免費享用!
課程來源:MIT
     

15.083J / 6.859 2004秋季課程:變數程式組合最佳化(Integer Program Combination Optimization, Fall 2004)

翻譯:蘇俊
編輯:陳玉侖

A figure illustrating Lagrangean duality.
拉格朗日(Lagrangian)對偶性的例子(取自第七課)。(圖片由Bertsimas教授提供。)
An example of Lagrangean duality (from Lecture 7). (Image courtesy of Prof. Bertsimas.)

課程重點

這門課的特點是包含全套的課堂講稿作業

This course features a full set of lecture notes and assignments.

課程描述

本課程對整數最佳化(integer optimization)的理論、演算法和應用做了全面的介紹。課程分為四部分:公式和鬆弛、整數最佳化的代數學和幾何學、整數最佳化的演算法,以及整數最佳化的延伸。

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.


技術需求

打開該課程網頁中的.zip檔需要解 壓縮軟體,例如WinzipR或StuffItR。.zip檔中含有的一些其他檔也需要特定軟體來打開。需要MATLABR打開和執行.m文件,而該課程 網頁中的.mod檔可以用許多程式打開。請參閱課程資料以獲得更多詳細指引或建議。課程網頁中的.dat檔可用許多軟體導入。請參閱課程資料以獲得更多的 詳細指引或建議。

File decompression software, such as Winzip® or StuffIt®, is required to open the .zip files found on this course site. The .zip files contain additional files which require software as well.
MATLAB® software is required to view and run the .m files on this course site. Any number of programs can be used to run the .mod files found on this course site. Please refer to the course materials for any specific instructions or recommendations. Any number of software tools can be used to import the .dat files found on this course site. Please refer to the course materials for any specific instructions or recommendations.

師資
講師:
Dimitris Bertsimas 教授
上課時數
教師授課:
每週2節
每節1.5小時

複習/實習課程:
每週1節
每節1小時
程度
研究所
回應
告訴我們您對本課程或「開放式課程網頁」的建議。
聲明
麻省理工學院開放式課程認可 開放式課程計畫(OOPS)的翻譯計畫,開放式課程計畫(OOPS)乃是運用其獨立團隊、獨立資源、獨立流程進行翻譯計畫之團隊。

所有麻省理工學院開放式課程之材料皆以麻省理工學院開放式課程創作共享授權發佈,所有之翻譯資料皆由開放式課程計畫(OOPS)所提供,並由其負翻譯品質之責任。

此 處麻省理工學院開放式課程之資料乃由 開放式課程計畫(OOPS) 譯為正體中文。麻省理工學院開放式課程在此聲明,不論是否遭遇或發現相關議題,麻省理工學院開放式課程、麻省理工學院教師、麻省理工學院校方並不對翻譯正 確度及完整性作保證。上述單位並對翻譯後之資料不作明示或默許對任一特定目的之適合性之保證、非侵權之保證、或永不出錯之保證。麻省理工學院校方、麻省理 工學院開放式課程對翻譯上之不正確不負任何責任。由翻譯所引發任何關於此等資料之不正確或其他瑕疵,皆由開放式課程計畫(OOPS)負全責,而非麻省理工 學院開放式課程之責。

原文聲明

 

課程大綱

本課程對整數最佳化的理論、演算法和應用做了全面的介紹,共分為四部分:

第一部分:公式化和鬆弛,第1-8課

討論如何將整數最佳化問題公式化,如何增強公式以提高鬆弛的品質,如何獲得理想公式、整數最佳化的對偶性,以及如何在實際中和理論上解決因而發生的鬆弛。

第二部分:整數最佳化的幾何學和代數學,第9-14課

逐步闡明格論,概述影響整數最佳化的代數幾何學思想,並討論整數最佳化的幾何學。這些課堂講授為發展演算法提供基礎。

第三部分:整數最佳化的演算法,第15-22課

闡述割平面方法、積分的基本方法、枚舉和啟發式方法和逼近演算法。我們處理方法的主要特點是根據演算和幾何運算法二所自然發展出的演算方法。

第四部分:整數最佳化的延伸,第23-25課

處理混合整數最佳化和強健離散最佳化。這兩個領域在實際應用中都非常重要,因為現實世界通常都同時有連續和離散變數,並有著不確定的元素,這需要用易處理的方法來解決。

講師

Dimitris Bertsimas教授

指定教科書

Bertsimas, Dimitris和Robert Weismantel.《整數最佳化》,Belmont, Massachusetts: 動態觀點出版社,2004年12月. 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%

 

 
日程表
Calendar 課 課程單元 重要日期
1 用整數變數建立模型
Modeling with Integer Variables

如何才是好公式
What is a Good Formulation

主題:公式化的效能
Theme: The Power of Formulations
 
2 增強公式化的方法
Methods to Enhance Formulations
 
3 增強公式化的方法II
Methods to Enhance Formulations II
 
4 理想公式化 I
Ideal Formulations I
 
5 理想公式化 II
Ideal Formulations II
 
6 理想公式化III
Ideal Formulations III
期中考試
Midterm exam
7 對偶性 I
Duality I
 
8 對偶性II 和有效演算法
Duality II and Efficient Algorithms
 
9 求解鬆弛
Solving Relaxations
 
10 格I
Lattices I
 
11 格II
Lattices II
 
12 格III
Lattices III
 
13-14 代數幾何學和整數最佳化
Algebraic Geometry and Integer Optimization
 
 

Bertsimas, Dimitris和Robert Weismantel.《整數最佳化》,Belmont, Massachusetts: 動態觀點出版社,2004年12月. ISBN: 0975914626. 正式出版前的版本。
以下進度表包括應當完成閱讀的日期。
The required text for this course is the prepublication edition of Bertsimas, Dimitris, and Robert Weismantel. Optimization over Integers. Belmont, Massachusetts: Dynamic Ideas, December 2004. ISBN: 0975914626.

The following schedule outlines due dates for reading completion.

表格題目(略)
Title for Table Goes Here 課 課程單元 閱讀資料
1 公式化
Formulations
第1章
Chapter 1
2 增強公式化的方法
Methods to Enhance Formulations
附錄A,第2章
Appendix A, Chapter 2
3 增強公式化的方法(續)
Methods to Enhance Formulations (cont.)
第2章
Chapter 2
4 理想公式化 I
Ideal Formulations I
第3章
Chapter 3
5 理想公式化II
Ideal Formulations II
第3章
Chapter 3
6 對偶性 I
Duality Theory I
第4章
Chapter 4
7 對偶性II
Duality Theory II
第4章
Chapter 4
8 求解鬆弛的演算法
Algorithms for Solving Relaxations
第5章
Chapter 5
9 格I
Lattices I
第6章
Chapter 6
10 格 II
Lattices II
第6章
Chapter 6
11 代數幾何學 I
Algebraic Geometry I
第7章
Chapter 7
  期中考試
Midterm Exam
講稿 1-11
Lecture 1-11
12 代數幾何學II
Algebraic Geometry II
第7章
Chapter 7
13 幾何學 I
Geometry I
第8章
Chapter 8
14 幾何學 II
Geometry II
第8章
Chapter 8
15 割平面方法 I
Cutting Plane Methods I
第9章
Chapter 9
16 割平面方法II
Cutting Plane Methods II
第9章
Chapter 9
17 積分基礎方法 I
The Integral Basis Method I
第10章
Chapter 10
18 積分基礎方法II
The Integral Basis Method II
第10章
Chapter 10
19 枚舉法
Enumerative Methods
第11章
Chapter 11
20 啟發性方法
Heuristic Methods
第11章
Chapter 11
21 演算法的複雜性和逼近演算法I
Complexity and Approximation Algorithms I
附錄 B, 第12章
Appendix B, Chapter 12
22 逼近演算法 II
Approximation Algorithms II
第12章
Chapter 12
23 混合整數規劃 I
Mixed Integer Optimization I
第13章
Chapter 13
24 混合整數規劃II
Mixed Integer Optimization II
第13章
Chapter 13
25 強健離散最佳化
Robust Discrete Optimization
第14章
Chapter 14
  期末考試
Final Exam
 

 

 

 

 
Lecture Notes 課# 課程單元 課堂講稿
1 用整數變數建立模型
Modeling with Integer Variables

如何才是好的公式化
What is a Good Formulation

主題:公式化的效能
Theme: The Power of Formulations

(英文PDF)
(英文DOC)
2 增強公式化的方法
Methods to Enhance Formulations

(英文PDF)
(英文DOC)
3 增強公式化的方法II
Methods to Enhance Formulations II

(英文PDF)
(英文DOC)
4 理想公式化 I
Ideal Formulations I

(英文PDF)
(英文DOC)
5 理想公式化II
Ideal Formulations II

(英文PDF)
(英文DOC)
6 理想公式化III
Ideal Formulations III

(英文PDF)
(英文DOC)
7 對偶性 I
Duality I

(英文PDF)
(英文DOC)
8 對偶性 II和有效演算法
Duality II and Efficient Algorithms

(英文PDF)
(英文DOC)
9 求解鬆弛
Solving Relaxations

(英文PDF)
(英文DOC)
10 格 I
Lattices I

(英文PDF)
(英文DOC)
11 格 II
Lattices II

(英文PDF)
(英文DOC)
12 格 III
Lattices III

(英文PDF)
(英文DOC)
13-14 代數幾何學和整數最佳化
Algebraic Geometry and Integer Optimization

(英文PDF)
(英文DOC)
 
 
Calendar 課 課程單元 復習主題 講稿
1 用整數變數建立模型
Modeling with Integer Variables

如何才是好的公式化
What is a Good Formulation

主題:公式化的效能
Theme: The Power of Formulations
   
2 增強公式化的方法
Methods to Enhance Formulations
復習多面體
Polyhedral Review

練習 2.10
Exercise 2.10
(PDF)
3 增強公式化的方法 II
Methods to Enhance Formulations II
第3章
Chapter 3

OPL 復習
OPL Review
(PDF)
4 理想公式化 I
Ideal Formulations I
評論作業
Homework Review
 
5 理想公式化II
Ideal Formulations II
   
6 理想公式化III
Ideal Formulations III
評論期中考試
Midterm Review
(PDF)
7 對偶性 I
Duality I

Lattices
(PDF)
8 對偶性 II 和有效演算法
Duality II and Efficient Algorithms
演算法 6.6
Algorithm 6.6
(PDF)
9 求解鬆弛
Solving Relaxations
Maple
Maple

家庭作業
Homework

SDP 公式化
SDP Formulation

YALMIP 與 SDPT3
YALMIP and SDPT3
(PDF)
10 格 I
Lattices I
錐面
Cones

整數生成集
Integral Generating Set

定理 8.5
Theorem 8.5

積分基礎方法
Integral Basis Method
(PDF)
11 格II
Lattices II
整數生成集
Integral Generating Set

幾何觀點
Geometric View
(PDF)
12 格III
Lattices III

Lattices
 
13-14 代數幾何學和整數最佳化
Algebraic Geometry and Integer Optimization
期末復習
Final Review
(PDF)

 

 

這部分的.zip檔需要用解壓縮軟體,例如Winzip®或是StuffIt®打開。.zip檔中含有的一些其他檔也需要特定軟體來打開。許多軟體可以用來導入這部分的.dat文件。這部分的.m檔需要用MATLABR執行。.mod檔則可以利用許多程式執行。
File decompression software, such as Winzip® or StuffIt®, is required to open the .zip files in this section. The .zip files contain additional files which require software as well. Any number of software tools can be used to import the .dat files in this section. MATLAB® software is required to run the .m files in this section. Any number of programs can be used to run this .mod file.

以下是問題集和答案
Problem sets and solutions are available below.

作業:作業文檔
Assignments: Assignment files 作業 答案 支援檔
問題集1Problem Set 1 (PDF) (PDF)  
問題集2Problem Set 2 (PDF) (PDF) (ZIP) (The ZIP file contains: 5 .prj files, 3 .dat files, and 3 .mod files)
問題集3Problem Set 3 (PDF) (PDF)  
問題集4Problem Set 4 (PDF) (PDF)  
問題集5Problem Set 5 (PDF) (PDF) knapsack.m (M)

knapsack.mod (MOD)
問題集6Problem Set 6 (PDF) (PDF)  

 

 

以下是期中測驗的題目與答案。
The midterm and midterm solutions are available below.

期中測驗
Midterm (PDF)

期中測驗答案
Midterm Solutions (PDF)

 

對「課程15.083J:變數程式組合最佳化」這門課有興趣的教育家、學生和自學者們,歡迎來和其他應用這個教材學習或教課的人在這個討論群組上互動。

這個服務是由麻省理工學院開放式課程提供,由猶他州立大學教育科技系的「開放持續學習機會研究群」所管理。世界各地的獨立學員可以互相連繫、協同合作、組織學習小組,及就利用麻省理工「開放式課程網頁」教材資源於他們正規或非正規教育學習時得到支援。

「開放式學習支援網」(Open Learning Support, 簡稱OLS)是一個著眼著眼於建立「社群軟體」的研究計劃,讓非正規學習社群利用現存公開的教材而組織起來。OLS基本前提是完整的教育機會必須讓使用者 能夠與能解答其問題或提供支援的其他人建立起溝通管道。贊助者一般只能提供免費開放的網頁教材,但很難提供這樣的社群管道。社群支援必須由其他使用者提 供。因此,OLS是:

在麻省理工「開放式課程網頁」以外獨立運作的。
需要使用者註冊並登入才能參與的
並不頒授任何學位或文憑的計劃
不提供與麻省理工或猶他州立大學教職人員直接連繫的管道
馬上來本課程《15.083J 變數程式組合最佳化》的Discussion Group for Course 15.083J / 6.859: Integer Program Combination Optimization討論群組看看吧。

「開放式學習支援網」是由The William and Flora Hewlett 基金會贊助提供。

 

 

回應

告訴我們這些 .ZIP檔如何協助你進行教導與學習。

.ZIP檔案中的課程內容與「麻省理工開放式課程」所出版的材料一樣,必需依照創作共享理念授權同意書規範。

為了離線或窄頻使用者,「麻省理工開放式課程」免費提供了完整的課程檔案下載。「麻省理工開放式課程」永遠是免費開放的電子出版品,你的捐款將可以讓我們維持更高的出版品質,及提供免費下載.ZIP檔案。請閱讀本頁以了解如何在經濟上支援我們。「麻省理工開放式課程」檔案下載的文件內容與課程網頁版本相同,讓你在本機上就可以瀏覽OCW課程材料。

課程下載

15-083JFall-2004.zip

 

 

下載課程的方法

點擊上方的連結來並開始下載 .ZIP 檔案。
使用解壓縮軟體,像是WinZipStuffIt來開啟.ZIP檔。解壓縮後,請依「麻省理工開放式課程」各課程內容需求,選用相應軟體來處理課程內容。你所下載的各課程首頁會列出所需軟體。
完成後,.ZIP即被下載並存放在你的電腦上。若已安裝解壓縮軟體,即可依軟體指示在電腦上開啟並將.ZIP檔案解開。

尋找並使用課程內容

開啟.ZIP並解壓縮後,就可使用瀏覽器開啟「麻省理工開放式課程」的html網頁。解壓後根目錄下的 Welcome.htm 檔案會將你導向該課程首頁。

.ZIP檔案中的課程內容與「麻省理工開放式課程」所出版的材料一樣,必需依照創作共享理念授權同意書規範。

常見問答集

下載一門課要多久?
麻省理工開放式課程的.ZIP檔案大小約介於 1MB 到 100MB間,多為 25MB-30MB。下載.ZIP檔案時可能佔用您一些時間,所需時間依您網路的連線速度而定。
為什麼.ZIP檔案裏少了某些課程材料,像是影片課程或模擬媒體?
像是影片、Java Applet等材料,以及一些沒有直接放在「麻省理工開放式課程」伺服主機上的特殊內容,在.ZIP裏亦不直接收錄,而是以連結的形式提供。你可以瀏覽內容網頁來下載這些影音檔案,請閱讀開放式系統說明網頁的我能夠把RealPlayer的影像檔案儲存到我的硬碟嗎?
如果下載課程時發生問題,我該找誰?

請寄信到 意見反應信箱ocw@mit.edu

留下您對本課程的評論
標題:
您目前為非會員,留言名稱將顯示「匿名非會員」
只能進行20字留言

留言內容:

驗證碼請輸入6 + 1 =

標籤

現有標籤:1
新增標籤:


有關本課程的討論

目前暫無評論,快來留言吧!

Creative Commons授權條款 本站一切著作係採用 Creative Commons 授權條款授權。
協助推廣單位: