Reduction of the complexity of linear models for combinatorial optimization problems via formulations in space of higher dimensions

在过去的几十年中，组合优化最成功的方法之一是将线性规划技术应用于适当表示可行解的点集的凸包。对于许多问题，相关的多面体（即，那些凸壳）已经被非常深入地研究。事实证明，在大多数有趣的情况下，这样的多面体的面的数量是指数的问题实例的大小，需要考虑指数的线性规划方法中的许多约束。虽然人们通常可以以隐式的方式有效地处理这些巨大的系统，但人们希望找到更小的系统，这些系统服务于相同的目标，并且可以显式地使用，例如，通过现成的软件。扩展公式的概念旨在通过将多面体表示为更高维的仿射投影来描述。事实上，对于一些问题，这在过去已经成功地做到了。这个项目的目标是扩展组合优化问题的扩展配方的概念的理解显着，并开发方法来构建这样的配方，以及确定这种配方的最小可能的大小的下限。虽然最佳线性表示的问题对于理解组合优化问题本身的线性优化方法的基本原理似乎很重要，但也希望项目内的工作将导致工具箱的扩展，用于在实践中建模离散优化问题。

One of the most successful approaches to combinatorial optimization over the last few decades has been to apply linear programming techniques to the convex hulls of sets of points suitably representing the feasible solutions. For many problems, the associated polytopes (i.e., those convex hulls) have been investigated very deeply. It turned out that in most interesting cases the number of facets of such a polytope is exponential in the size of the problem instance, requiring to take into account exponentially many constraints in the linear programming approach. Though often one can deal with these huge systems efficiently in an implicit way, it is desirable to find much smaller systems that serve the same goal and can be used explicitly, e.g. by off-the-shelf software. The concept of extended formulations aims at this by representing polytopes as affine projections of higher dimensional ones that are much simpler to describe. Indeed, for several problems this has been done successfully in the past. The goal of this project is to extend significantly the understanding of the concept of extended formulations for combinatorial optimization problems and to develop methods to construct such formulations as well as to determine lower bounds on the smallest possible sizes of such formulations. While the question for best possible linear representations seems to be important for understanding the fundamentals of the linear optimization approach to combinatorial optimization problems per se, it is also hoped that work within the project will lead to extensions of the toolbox for modeling discrete optimization problems in practice.