Research Initiation: Polyhedral Theory and Algorithms for Two NP-Complete Problems

研究启动：两个NP完全问题的多面体理论和算法

• 批准号: 8809053
• 负责人: E. Andrew Boyd
• 金额: --
• 依托单位: William Marsh Rice University
• 依托单位国家: 美国
• 项目类别: Continuing grant
• 财政年份: 1988
• 资助国家: 美国
• 起止时间: 1988-07-01 至 1991-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=8809053&HistoricalAwards=false
• 关键词: Research; Initiation; Polyhedral; Theory; Algorithms

Precedence constraints arise frequently in discrete optimization problems. Polyhedral theory and computational experience both suggest that integer programs defined largely by precedence constraints have structure that can be exploited to develop good polyhedral-based algorithms for their solution. Two important integer programming problems with precedence constraints are the precedence-constrained knapsack problem and the plant location problem. The PI will develop new polyhedral results for these NP-complete problems so that together with existing polyhedral results fast, efficient algorithms for their solution can be implemented. Special attention will be given to the development of parallel algorithms. Beyond providing operational algorithms that can be used to solve actual applications of these two problems, the work will extend the known theory of polyhedral combinatorics.

优先约束在离散优化问题中经常出现。 多面体理论和计算经验都表明，主要由优先约束定义的整数程序具有可用于为其解决方案开发良好的基于​​多面体的算法的结构。 两个重要的具有优先约束的整数规划问题是优先约束背包问题和工厂位置问题。 PI 将为这些 NP 完全问题开发新的多面体结果，以便与现有的多面体结果一起快速、高效地实现其解决方案的算法。 将特别关注并行算法的开发。 除了提供可用于解决这两个问题的实际应用的运算算法之外，这项工作还将扩展已知的多面体组合理论。