整數規劃

Abstract

本課程是由交通大學 管理學院 運輸與物流管理學系提供。

本錄影課程為復旦大學孫小玲教授應邀授課，授課內容與課程大綱稍有不同。

課程簡介 整數規劃(Integer Programming)是數學規劃的重要分支之一，是離散最優化的基礎和重要組成分，整數規劃模型和算法在管理科學、經濟、金融工程、工業管理和其他領域有廣泛的應用。自從運籌學創始人之一 Dantzig與Fulkerson 和 Johnson等人在上世紀五十年代發表利用混合整數規劃方法求解旅行售貨員問題(TSP)的論文以來，經過五十多年的研究，整數規劃已發展成為最優化方法用於解決管理決策問題的成功典範之一，特別是基於分枝定界和各種鬆弛技術的算法已日趨成熟並開發為各種商業優化建模和算法軟體，由Bixby等人研發的混和線性整數規劃軟體CPLEX和相應的建模環境GAMS 和 AIMMS使混和線性整數規劃在學術界和工業界得到了廣泛的應用。近年來，錐優化方法特別是半定規劃多項式時間算法的發展給為求解NP-難整數規劃問題提供了新的思路和方法，在二次0-1規劃和多項式規劃領域都取得了不少突破，整數規劃與錐優化方法的結合是近年來國際運籌學和最優化研究的熱點之一。 本課程旨在講授整數規劃的核心內容，以線性整數規劃的理論和算法為主，同時涵蓋一部分非線性整數規劃內容。本課程強調整數規劃問題建模與應用相結合，理論與算法相結合，經典理論和前沿研究問題相結合。 課程目標

用整數規劃建模和利用通用整數規劃軟體求解； 掌握整數規劃的基本算法思想和計算複雜性概念； 理解整數規劃高級算法的思想，經過進一步的學習能設計算法求解具有特殊結構的整數規劃問題。 課程章節

單元主題

Module 1 Introduction to Integer Programming

Modeling and application of integer programming

Branch-and-bound methods

Introduction and demo of integer programming software

Module 2 Theory of Integer Programming

Computational complexity theory

Polyhedral theory and total unimodularity

Module 3 Branch-and-bound framework and revisited

Integer programming problems and methods for graphs and network flows

Cutting-plane method

Dynamic programming

Module 4 Advanced Algorithms

Lagrangian relaxation and decomposition

Bender decomposition and Dantzig-Wolfe decomposition

Column generation

Branch-and-cut method

Module 5 0-1 Quadratic Programming

Maximum-cut problem, SDP relaxation and randomized scheme

0-1 quadratic knapsack problem 課程書目

Xiaoling Sun, Duan Li, Integer Programming, Science Press, Beijing, 2010, 1st edition, (in Chinese)

授課對象：大學生、研究生