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.