課程名稱 |
整數與組合最佳化 INTEGER AND COMBINATORIAL OPTIMIZATION |
開課學期 |
98-2 |
授課對象 |
工學院 機械工程學研究所 |
授課教師 |
黃奎隆 |
課號 |
IE7020 |
課程識別碼 |
546 M6040 |
班次 |
|
學分 |
3 |
全/半年 |
半年 |
必/選修 |
選修 |
上課時間 |
星期二6,7,8(13:20~16:20) |
上課地點 |
國青233 |
備註 |
總人數上限:20人 |
Ceiba 課程網頁 |
http://ceiba.ntu.edu.tw/982IP |
課程簡介影片 |
|
核心能力關聯 |
核心能力與課程規劃關聯圖 |
課程大綱
|
為確保您我的權利,請尊重智慧財產權及不得非法影印
|
課程概述 |
The course covers fundamental integer programming techniques, including cutting plane methods, branch-and-bound enumeration, Bender’s decomposition, Lagrangain relaxation/decomposition, and heuristic/meta-heuristic programming. It also covers special techniques for solving well-known combinatorial problems, such as knapsack problem and the set covering/partition problem. This course will include the following topics:
Tentative outline:
1. Introduction to Integer Programming (IP)
2. IP modeling and applications
3. The beale Tableau
4. Using Linear programming to solve IP problems
5. Cutting plane techniques
6. Branch-and-Bound enumeration
7. Search enumeration
8. Bender’s Decomposition
9. Lagrangian Relaxation/Decomposition
10. Heuristic Algorithms
11. Combinatorial problems: knapsack problem and the set covering/partition problem
|
課程目標 |
The course primarily focuses on study of Integer Programming and gives an overview of classical methods about problem formulations and solving. The goal of this course is to provide students some understanding such as why some problems are difficult to solve, how they can be reformulated to yield better results, and how effective different algorithms can be. |
課程要求 |
Your grade in the course will be determined by homework (25%), midterm exam (25%), final exam (25%) and project (25%). The requirements in details are described as follows:
(83dc) Homework will be assigned every two weeks and the assignments need to be done independently. Late submissions are not accepted except a prior approval is received from the instructor.
(83dc) There are one midterm and one final exam.
(83dc) There is a final project which helps students comprehend the class material and apply them to practical problems or real cases. The project may consist of a literature review for an application area, a research problem, or a computational study. 2 to 3 students (may vary upon the class size) form a group. Prepare a 20-min presentation and submit a report in the last class
|
預期每週課後學習時數 |
|
Office Hours |
|
指定閱讀 |
H.M. Salkin and K. Mathur, Foundations of Integer Programming, North-Holland, New York, 1989 |
參考書目 |
G.L. Nemhauser and L.A. Wolsey, Integer and Combinatorial Optimization, Wiley 1988.
L.A. Wolsey, Integer Programming, Wiley 1998.
|
評量方式 (僅供參考) |
|
|