组合优化问题的组合：问题、算法和复杂性

项目名称： 组合优化问题的组合：问题、算法和复杂性

项目编号： No.11371216

项目类型： 面上项目

立项/批准年度： 2013

项目学科： 数理科学和化学

项目作者： 王振波

作者单位： 清华大学

项目金额： 50万元

中文摘要： 一些经典的组合优化问题，如排序问题、网络流问题、网络设计问题、背包问题、装箱问题、最大割问题等，传统上都是作为相对独立的方向而被深入地研究，而实际遇到的问题往往会涉及到多个不同的组合优化问题。本项目研究两个组合优化问题的组合，其中一个组合优化问题提供约束条件，而另一个组合优化问题决定最终优化的目标。组合优化问题的组合基于一些的经典组合优化问题，但又具有全新的结构，在问题、算法和复杂性等方面都蕴含着丰富的研究内容，而在文献中却很少相关的研究。本项目的研究将一些彼此独立的经典优化问题有机地联接在一起，扩大了组合优化领域的研究范围。本项目的研究包含三个主要方面：1. 根据理论和应用的需要，建立不同的优化问题的组合模型；2. 通过探索各个优化问题的方法和理论之间的联系，发现相应的组合问题所具有的内在性质，并建立相应的理论；3.分析组合问题的计算复杂性并设计有效的算法。

中文关键词： 组合最优化；计算复杂性；算法设计与分析；优化问题的组合；

英文摘要： In the history of combinatorial optimization, a number of classical combinatorial optimization problems have been studied independently, e.g. machine scheduling problem, network flow problem, network design problem, knapsack problem, bin packing problem a

英文关键词： combinatorial optimization；computational complexity；algorithm design and analysis；combination of optimization problems；