离散优化

本课程研究离散或整数类的优化问题,主要内容包括:第一部分,离散优化的基本概念和基本理论,从多面体组合理论角度,引入合法描述、更佳描述和理想描述的概念,通过典型的离散优化问题的建模,介绍获得更佳描述的方法,并系统阐述理想描述的判别和证明;第二部分,离散优化算法的基本知识,如复杂性、最优性、松弛以及上下界等,以及求解离散优化问题的主要算法,包括割平面法、动态规划、分支定界法、列生成法等,重点分析相关优化算法的基本思想和构造;第三部分,以讨论课的形式,研讨离散优化理论应用于航空公司调度、生产调度、空中交通管理、供应链管理、无线通信网络规划和超大规模集成电路布局规划等领域的模型和算法。