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