Polyhedral Methods in Integer and Combinatorial Optimization

本研究解决了整数和组合规划的几个基本特征，这是一种具有实际和潜在应用于各种现实世界情况的理论和方法。多面体方法，旨在凸化各种非凸组合结构已被证明是一种成功和有前途的方法。本研究解决了多面体组合中的几个基本开放问题，如：什么时候线性规划可以解决包装或覆盖问题，哪些线性不等式对于包装或覆盖多面体的定义或旅行商多面体的定义是必不可少的；以及更直接的实际问题，如：优先约束的旅行商问题或有能力的车辆路线问题的最佳表述是什么，哪些团问题是多项式可解的，解决集合覆盖、作业车间调度和车辆路线问题的最有效近似方法是什么。该项目的预期结果是对所调查问题的结构有新的、有用的见解，并为解决问题提供更有效的方法。

This research addresses several basic features of integer and combinatorial programming, a theory and methodology with actual and potential applications to a great variety of real world situations. Polyhedral methods, aimed at convexifying various nonconvex combinatorial structures have proved themselves as a successful and promising approach. This research addresses several basic open questions in polyhedral combinatorics, like: when is a packing or covering problem solvable by linear programming, which linear inequalities are essential to the definition of a packing or covering polyhedron, or to that of the traveling salesman polytope; as well as more immediately practical questions, like: what is the best formulation of a precedence-constrained traveling salesman problem or a capacitated vehicle routing problem, which clique problems are polynomially solvable, what are the most efficient approximation methods for solving set covering, job shop scheduling, and vehicle routing problems. The expected results of this project are new, useful insights into the structure of the problems investigated and more efficient methods for their solution.