Research On Combinatorial Optimization Problems Under Linear Constraints

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 scheduling problems,the weights and values of items in knapsack problems,and the sizes of items in bin packing problems.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.In this dissertation,we consider several combinatorial optimization problems under linear constraints,that is,the parameters of a problem should satisfy a system of linear constraints,thus are part of the decision.We mainly study scheduling problem under linear constraints,knapsack problem under linear constraints,bin packing problem under linear constraints,etc.Such 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.We first formally define several combinatorial optimization problems under linear constraints,and provide 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 and be applied to our problem directly.Based on the techniques of linear programming and combinatorial optimization,we discuss the computational complexity for different setting of these problems,and design polynomial-time algorithms or approximation algorithms for them.We observe that for some intractable combinatorial optimization problems,e.g.,parallel machine scheduling and bin packing problem,the corresponding problems under linear constraints are polynomial-time solvable in certain cases,such as when the number of linear constraints is few;for some tractable combinatorial optimization problems,e.g.,the shortest path problem without negative edges,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,we introduce the concept of combinatorial optimization problems under linear constraints,and construct various classical combinatorial optimization problems under linear constraints.2.We explore the structures and properties of the combinatorial optimization problems under linear constraints,and connect them with linear programming and classical combinatorial optimization problems.3.We investigate the computational complexity for various setting of these problems,and design the corresponding polynomial-time algorithms or approximation algorithms.