权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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

通过高维空间中的公式降低组合优化问题的线性模型的复杂性

基本信息

批准号：
214884184
负责人：
Professor Dr. Volker Kaibel
金额：
--
依托单位：
Institut für Mathematische Optimierung (IMO)
依托单位国家：
德国
项目类别：
Research Grants
财政年份：
2012
资助国家：
德国
起止时间：
2011-12-31 至 2018-12-31
项目状态：
已结题

来源：
https://gepris.dfg.de/gepris/projekt/214884184?language=en
关键词：
Reduction complexity linear models combinatorial

项目摘要

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.

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