AF - Limitations of convex relaxations in combinatorial optimization

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

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.