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.