组合优化是运筹学的一个重要研究分支，包含很多经典问题，如排序问题、网络流问题、背包问题、装箱问题等。每个组合优化问题都有各自的参数，如排序问题中工件的加工时间、背包问题中物品的权重和价值、装箱问题中物品的大小等。在传统的组合优化研究中，这些参数一般独立于问题的决策，由外部环境预先给定。在实际的应用中，决定这些参数往往也是一个需要优化的问题，例如参数需要满足一些资源的约束或满足一定的供求关系。本文研究一些线性约束下的组合优化问题，即组合优化问题的参数需要满足一些线性约束，因此也是决策的一部分。本文研究的问题包括线性约束下的排序问题、线性约束下的背包问题、线性约束下的装箱问题等。这些问题具有全新的结构，在实际生活中有广泛的应用场景，蕴含着丰富的研究内容，但文献中却很少有相关的研究。本文首先给出了这些线性约束下的组合优化问题的具体模型，提供它们的研究动机和实际背景。很多线性约束下的组合优化问题，都能自然地表示成一些复杂的数学规划问题，如混合双线性规划问题。一般而言，这些数学规划问题都是十分困难的，不容易直接应用它们的结论去求解本文研究的问题。利用线性规划和组合优化的技术，本文分析这些问题的计算复杂性和提出相应的算法。本文通过研究发现，有一些原来困难的组合优化问题，例如平行机排序问题、装箱问题等，其线性约束下的问题在某些情况下，如约束的个数是常数时是多项式可解的；也有一些原来可解的组合优化问题，例如不含负权的最短路问题等，其线性约束下的问题一般情况下是困难和难以近似的。本文主要的创新点总结如下：1. 根据实际应用需要，提出了线性约束下的组合优化问题，并建立了一系列不同的线性约束下的组合优化问题。2. 研究线性约束下的组合优化问题的结构与性质，和它们与线性规划、组合优化问题的联系。3. 分析这些问题在不同情形下的计算复杂性，并设计和分析相应的多项式时间算法或近似算法。
Combinatorial optimization is an important field of operations research, which contains a lot of classical problems, such as machine scheduling problem, network flow problem, knapsack problem and bin packing problem. Each combinatorial optimization problem has its own parameters, for example, the processing times of jobs in schedulingproblem, the weights and values of items in knapsack problem, and the sizes of items in bin packing problem. In the literature, those parameters are usually assumed to be given in advance, and are independent of the decision.In a variety of real-world applications, determining those parameters may also be an optimization decision, e.g., the values of the parameters should satisfy several resource constraints or some demand requirements. This dissertation considers several combinatorial optimization problems under linear constraints, that is, the parameters of a problemshould satisfy a system of linear constraints, thus are part of the decision. This dissertation studies scheduling problem under linear constraints, knapsack problem under linear constraints, bin packing problem under linear constraints, etc. These problems are widely appeared in the real world, and involve numerous interesting research problems. However, to the best of our knowledge, there are few studies concerned about them in the literature. This dissertation first formally defines several combinatorial optimization problems under linear constraints, and then provides their practical application scenarios. The natural formulation for a combinatorial optimization problem under linear constraints is usually a complicated mathematical programming problem, such as a mixed integer bilinear programming problem, which is generally hard to solve. Based on the techniques of linear programming and combinatorial optimization, this dissertation discusses the computational complexity for di erent setting of these problems, and designs polynomial-time algorithms or approximation algorithms for them. For some intractable combinatorial optimization problems, e.g., parallel machine scheduling and bin packing problem, the corresponding problems under linear constraints are polynomial-time solvablein certain cases, such as when the number of linear constraints is a fixed constant; for some tractable combinatorial optimization problems, e.g., the shortest path problem without negative edge weights, the corresponding problems under linear constraints are in general intractable and hard to be approximated.The main contributions of this dissertation are described as follows:1. Based on real applications, this dissertation introduces combinatorial optimization problems under linear constraints, and studies various combinatorial optimization problems under linear constraints.2. This dissertation studies the structures and properties of the combinatorial optimization problems under linear constraints, and finds the relationship between linear programming and combinatorial optimization problems.3. This dissertation investigates the computational complexity for various setting of these problems, and designs and analyzes the corresponding polynomial-time algorithms or approximation algorithms.
