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

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 and max cut problem, etc. In real applications, the decision-makers always face to a system involved several characteristics among more than one well-known combinatorial optimization problems. This project studies the combination of two combinatorial optimization problems in which one problem provides the feasibility constraints whereas the other decides the objective function. The combination problem is based on some classical combinatorial optimizations, but it appears different aspects in combinatorial structure, and involves numerous challenging problems in model, algorithm and computational complexity. To our knowledge, little research studied the combination of optimization problems in literature. This project bridges different directions of combinatorial optimization, and extends the scope of this field. This project includes three main research topics. 1. Based on real applications and theoretical interests, we will construct variant combination problems; 2. we will investigate the methods and theories for different combinatorial optimization problems, and discover the underlying properties of the corresponding combination problems; 3. we will analyze the computational complexity of the combination problems, design efficient algorithms and analyze their performance.

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

本项目研究两个组合优化问题的组合，其中一个组合优化问题提供约束条件，而另一个组合优化问题决定最终优化的目标。组合优化问题的组合基于一些的经典组合优化问题，但又具有全新的结构，在问题、算法和复杂性等方面都蕴含着丰富的研究内容，而在文献中却很少相关的研究。本项目的研究将一些彼此独立的经典优化问题有机地联接在一起，扩大了组合优化领域的研究范围。本项目的研究成果包含：1. 对于平行机和覆盖问题的组合问题，我们给出了组合优化问题组合的一个统一框架，设计并分析了多个近似算法；2. 研究流水车间排序问题和最短路问题的组合问题；3. 提出了平行机排序和线性规划的组合问题。