AF - Limitations of convex relaxations in combinatorial optimization

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

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.