整数规划法与组合优化
学分：6
很多实际问题，如列车和航班时刻表、车辆路线、生产规划、资源管理、通讯和网络设计等，均可以通过整数或混合整数程序建模。
本课程将讲述整数规划问题的综合理论及精确和近似算法以及其广泛应用。首先，本课程将讲述整数规划的公式和例题。其次，本课程将讲述最优化原则、松弛法、界限和总幺模性。基于这些基本概念，本课程将讲述整数规划的某些计算方法，如动态规划法、分支定界、有效不等式、平面分割法及启发式方法。
本课程可由课程讲师自行决定选择教授用于解答整数规划问题的现代半正定规划（SDP）方法。在第二部分，本课程将系统性论述用于解答离散问题的优化方法，并通过该方法解答实际问题，如寻找穿过交通网络的最廉价路径或高效地将资源用于目标问题。本课程还
将讲述计算复杂性的概念，该概念旨在根据不同难度将问题分类并导向算法效率概念。
在本课程结课时，学生应能够：
• 学生应理解整数规划问题存在于各个领域，如工程学、经济学与管理学。他们应理解整数规划的基本理论和算法，并掌握通常难以解答整数规划问题的原因
• 他们应理解如何运用整数规划的基本方法（分支界限法、松弛法、平面分割法、启发式方法等），以求解为各种管理问题和其他实际问题而构建的整数规划模型
• 他们应有能力利用整数规划（IP）问题的特殊结构高效解答此类问题，并解释计算得出的答案
• 他们应有能力解释离散和连续优化之间的区别，并理解整数规划问题解答方法的独特性
• 学生应有能力为实际问题建立离散优化公式，并运用精确和近似算法解答问题，如最短路径、网络流量、交通问题、背包问题和巡回销货员问题；他们应证明自己对
计算复杂性及其简化以及证法（某些问题属于非确定多项式难题）的理解；他们将理解拟阵理论在优化程序中的作用。
Integer Programming and Combinatorial Optimization 整数规划法与组合优化
Credits:6
Many practical problems such as train and airline scheduling, vehicle routing, production planning, resource management, telecommunications and network design can be modelled as integer or mixed-integer programs.
This module presents a comprehensive theory and exact and approximate algorithms for integer programming problem and a wide variety of its applications. This module will start with formulations and illustrative examples of integer programs. Following that, the optimality, relaxation, bound and total unimodularity will be introduced. Based on these fundamental concepts, some computational methods of integer programing such as the dynamic programming, branch and bound, valid inequalities and cutting planes, and heuristic methods will be presented.
Modern semi-definite programming (SDP) technique dealing with integer programming is optional and at the discretion of the lecturer in charge. The second part of this module presents a systematic survey of methods of optimisation for problems with discrete features, and relates them to practical problems such as finding the cheapest route
through a transportation network or efficiently assigning resources to objectives. The concept of computational complexity leads to a classification of problems into grades of hardness and to the concept of the efficiency of an algorithm.
By the end of this module, students should be able to:
• Students will understand that integer programming problems arise in many fields such as engineering, economics, and management. They will understand basic theory and algorithms for integer programs and understand why integer programs are hard to handle in general.
• They will know how to use the basic techniques of integer programming (branch bound, relaxation, cutting-plane, heuristics, etc.) to solve integer programming models for a variety of managerial and other practical problems.
• They will be able to solve an IP problem efficiently by taking into account the particular structure of the problem and interpret the results obtained.
• They will be able to explain the difference between discrete and continuous optimisation, and understand the uniqueness of the techniques for solving integer programs.
• Students will be able to formulate practical problems as discrete optimisation and apply exact or approximate algorithms to problems such as shortest path, network flows, transportation, knapsack and travelling salesman; show an understanding of computational complexity and its reduction and of proofs that certain problems are NP hard; they will understand the role of matroids in optimisation.
