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

点击翻译按钮获取中文摘要

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.