线性约束下的组合优化问题研究

Combinatorial optimization is an important field of operations research, and contains many classical problems, e.g., machine scheduling problem, network flow problem, knapsack problem, bin packing problem, etc. Every combinatorial optimization problem has its own parameters, e.g., the processing times in scheduling problems and the sizes of items in bin packing problem. In the literatures, it is always assumed that those paremeters are given in advance, and are independent of the decision.This project considers that those paremeters are determined by a system of linear constraints, and hence are part of the decision. This novel problem is motivated by various real-world application scenarios. Our study will connect combinatorial optimization and linear optimization, and involves numerous interesting problems in model, algorithm and computational complexity. To our knowledge, few studies concerned about the combinatorial optimization problems under linear constraints in literatures. This project includes three main research topics. 1. Based on real applications and theoretical interests, we will construct variant combinatorial optimization problems under linear constraints; 2. Based on the theory and techniques of comibinatorial optimization and linear programming, we will investigate the underlying properties of the combinatorial optimization problems under linear constraints; 3. we will analyze the computational complexity of these problems, design and analyze corresponding algorithms.

组合优化是运筹学的一个重要研究分支，包含很多经典问题如排序问题、网络流问题、背包问题、装箱问题等。每个组合优化问题都有各自的参数，如排序问题中工件的加工时间，装箱问题中物品的大小等。在传统的组合优化研究中，这些参数一般独立于问题的决策，由外部预先给定。在实际的应用中，决定这些参数往往也是一个需要优化的问题。本项目研究线性约束下的组合优化问题，即组合优化问题的参数需要满足一些线性约束。本项目结合了组合优化和线性规划，具有全新的结构，在问题、算法和复杂性等方面都蕴含着丰富的研究内容，而在文献中却很少相关的研究。本项目的研究包含三个主要方面：1. 根据理论和应用的需要，建立不同的线性约束下的组合优化问题；2. 应用组合优化及线性规划的理论，发现线性约束下的组合优化问题所具有的内在性质；3. 分析各个问题的计算复杂性并设计相应的算法。

本项目研究线性约束下的组合优化问题，即组合优化问题的参数需要满足一些线性约束。本项目结合了组合优化和线性规划，具有全新的结构，在问题、算法和复杂性等方面都蕴含着丰富的研究内容。本项目的研究包含以下几个主要方面：1. 整理和改进了一些前期的工作成果，如背包问题的组合问题；2.同类平行机排序问题，其中机器速度满足线性约束；3. 线性约束下一些和图有关的优化问题；4. 线性约束下2阶段流水车间排序问题；5. 本项目支持下进行一些相关研究：品类优化(Assortment Optimization)问题；资源配置问题(resource allocation)问题等。.项目按计划执行，达到预想研究目标。