課程名稱 |
離散最佳化 Discrete Optimization |
開課學期 |
102-1 |
授課對象 |
工學院 工業工程學研究所 |
授課教師 |
張時中 |
課號 |
EE5077 |
課程識別碼 |
921EU3410 |
班次 |
|
學分 |
3 |
全/半年 |
半年 |
必/選修 |
選修 |
上課時間 |
星期五2,3,4(9:10~12:10) |
上課地點 |
電二225 |
備註 |
本課程以英語授課。 總人數上限:40人 |
Ceiba 課程網頁 |
http://ceiba.ntu.edu.tw/1021_do |
課程簡介影片 |
|
核心能力關聯 |
本課程尚未建立核心能力關連 |
課程大綱
|
為確保您我的權利,請尊重智慧財產權及不得非法影印
|
課程概述 |
1. Course Overview, Algorithms and Complexity and Basics of Optimization.
2. Linear Programming: Problems, Properties and Simplex Algorithms
3. Duality Theorem and Sensitivity
4. Interior Point Methods for LP
5. Network Representation and Shortest Path Algorithms
6. Distributed Shortest Path Algorithms
7. Minimum Spanning Tree Problem
8. Maximum Flow and Minimum Cost Flow Algorithms
9. Integer Programming Algorithms
10.The Traveling Salesman Problem and Knapsack Problem
11.Simulated Annealing
12.Tabu Search
13.Genetic Algorithms
14.Artificial Neural Networks for Optimization
15.Specific Applications
|
課程目標 |
- To introduce to students the theory, models, analysis, approximations and algorithms of optimization over discrete variables
- To guide students to apply the theory to and design methods for solving electrical engineering and computer science problems. |
課程要求 |
Grading
Homework 30% Mid-term Exam 35% Term Project 35%
Participation 5%
|
預期每週課後學習時數 |
|
Office Hours |
另約時間 |
指定閱讀 |
|
參考書目 |
教科書: C. H. Papadimitriou, K. Steiglitz, Combinatorial Optimization:Algorithms and Complexity, Prentice Hall, 1982.
參考書目: E. Aarts, J. K. Lenstra, eds., Local Search in Combinatorial Optimization, Wiley, 1997.
|
評量方式 (僅供參考) |
|
週次 |
日期 |
單元主題 |
第1週 |
9/14,9/16 |
Course Overview, Algorithms and Complexity and Basics of Optimization. |
第2週 |
9/21,9/23 |
Algorithms and Complexity;Linear Programming: Problems, Properties, and Simplex Algorithm in Matrix Form |
第3週 |
9/28,9/30 |
Linear Programming: Simplex Algorithms, Duality and Sensitivity |
第4週 |
10/05,10/07 |
Complementary slackness, sensitivity, Karmakar's interior point algorithm |
第5週 |
10/12,10/14 |
Introduction to Network Optimization Problem, Network representation |
第6週 |
10/19,10/21 |
Minimum Spanning Tree Problems
–Problem description and greedy algorithm
–Mathematical Formulation
–Optimality proof
Maximum Flow Problem
–Formulation
–Minimum cut, max flow and dualityMaximum Flow Problem
Total Unimodularity
–Minimum cut, max flow and duality |
第7週 |
10/26,10/28 |
minimum cost networkflow problem - negative cycle canceling; MCNFP and other network problem conversion. |
第8週 |
11/02,11/04 |
matching problems and algorithms; Introduction to branch and bound; |
第9週 |
11/09,11/11 |
Traveling Salesman Problem - Branch and Bound(B&B), Cutting Plane Method(Gomory’s Cut); Introduction to scheduling problems; |
第10週 |
11/16,11/18 |
Scheduling problems and algorithms: single machine, parallel machine, flow shop scheduling |
第11週 |
11/23,11/25 |
Introduction of iLog optimization tool suites CPLEX; 11/25 midterm exam |
第12週 |
11/30,12/02 |
Parallel Machine Scheduling; Flow Shop Scheduling and Rescheduling
|
第13週 |
12/07,12/09 |
Local Search;Meta-Heuristic Search; Specific Search Strategies;Simulated Annealing; |
第14週 |
12/14,12/16 |
Simulated Annealing(Cont.); Stochastic Machines; Convergence Analysis; Genetic Algorithm; |
第15週 |
12/21,12/23 |
Genetic Algorithm; Monte Carlo Simulation -based Optimization |
第16週 |
12/28,12/30 |
Stochastic optimization problem
Stochastic simulation (Monte Carlo)
Efficient techniques:
Ordinal Optimization (OO)
Optimal Computing Budget Allocation (OCBA)
Application to scheduling semiconductor fabs |
第17週 |
1/04,1/06 |
Introduction to constraint programming: modeling, constraint propagation, search, best solution |
第18週 |
01/11, 13/2011 |
no class; term project preparation; |
第19週 |
01/19, 20/2011 |
Term project presentations |
|