Polyhedral Methods in Integer and Combinatorial Optimization

整数和组合优化中的多面体方法

• 批准号: 8901495
• 负责人: Egon Balas
• 金额: $ 18.39万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1989
• 资助国家: 美国
• 起止时间: 1989-08-15 至 1993-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=8901495&HistoricalAwards=false
• 关键词: Polyhedral; Methods; Integer; 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.

本文研究了整数的几个基本特征 和组合编程，一种理论和方法， 各种各样的真实的 世界局势。 多面体方法，旨在凸化 各种非凸组合结构已经证明了它们自己 是一个成功且有前途的方法。 本研究解决 多面体组合学中的几个基本的开放性问题，例如： 什么时候填充或覆盖问题可由线性 规划，其中线性不等式是必不可少的， 包装或覆盖多面体的定义，或 旅行推销员多面体;以及更直接 实际问题，如：什么是最好的公式， 优先约束的旅行商问题或 有能力限制的车辆路径问题， 多项式可解，什么是最有效的近似 解决集合覆盖的方法，车间作业调度， 车辆路径问题。 本项目的预期成果 是对问题结构的新的、有用的见解， 研究和更有效的方法来解决它们。