AF - Limitations of convex relaxations in combinatorial optimization

AF - 组合优化中凸松弛的局限性

• 批准号: 1420180
• 负责人: Thomas Rothvoss
• 金额: $ 33.11万
• 依托单位: University of Washington
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-07-15 至 2018-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1420180&HistoricalAwards=false
• 关键词: AF; Limitations; convex; relaxations; combinatorial

In our modern society, planning and scheduling decisions such as those made to optimize airplane scheduling, route planning, and production planning increasingly rely on computer algorithms. Many popular methods to solve these often computationally hard problems are based on so-called linear programming relaxations or, more generally, on convex programming relaxations. In this project, the PI and the supported graduate student will study the theoretical power and limitations of such convex relaxations for various optimization problems. One goal is to discover new techniques to algorithmically extract near-optimal solutions from those relaxations and hence certify the quality of those relaxations. Another goal is to show lower bounds which prove that, for some problems, no relaxation of a certain type and quality exists. This will yield a better understanding of techniques that are widely used in industry to solve real-world optimization problems. In addition, finding lower bounds and fundamental limitations will help researchers and practitioners avoid wasting precious effort trying to improve techniques that have reached their limits and, instead, will focus their attention on finding alternative approaches for improved algorithms. The PI is also committed to making results available to a broad audience of students and researchers via lecture notes, survey papers, and tutorials.

在我们的现代社会中，计划和调度决策，例如优化飞机调度，路线计划和生产计划的决策越来越依赖计算机算法。 许多流行的方法来解决这些经常在计算上的硬性问题是基于所谓的线性编程放松，或者更普遍地是在凸编程放松身上。 在这个项目中，PI和受支持的研究生将研究这种凸放松的理论能力和局限性，以解决各种优化问题。 一个目标是发现新技术，以从这些放松身心中提取近乎最佳的解决方案，从而证明这些放松的质量。 另一个目标是显示下限，证明对于某些问题，不存在某种类型和质量的放松。 这将更好地了解行业中广泛用于解决现实世界优化问题的技术。 此外，找到下限和基本限制将有助于研究人员和从业者避免浪费宝贵的努力，试图改善已达到限制的技术，而将注意力集中在寻找改进算法的替代方法上。 PI还致力于通过讲义，调查文件和教程为广大的学生和研究人员提供结果。

项目成果

A (1+epsilon)-Approximation for Makespan Scheduling with Precedence Constraints Using LP Hierarchies

使用 LP 层次结构的具有优先约束的 Makespan 调度的 A (1 epsilon) 近似

• DOI: 10.1137/16m1105049
• 发表时间: 2019
• 期刊: SIAM Journal on Computing
• 影响因子: 1.6
• 作者: Levey, Elaine;Rothvoss, Thomas
• 通讯作者: Rothvoss, Thomas