Strengths and Limitations of Formulations for Combinatorial Optimization Problems.

组合优化是数学优化的一个重要领域。它反映了许多现实生活中的问题。这类问题的常见例子是开发道路网络或以最佳方式将用户的请求与服务器匹配。解决这些问题的一种方法是开发组合算法，但这种方法通常是特定于问题的，并且在包括额外约束方面不鲁棒。处理这些问题的另一种方法是将它们用凸规划或整数规划来表示。这使我们能够从凸规划和整数规划的丰富理论中汲取经验。这一策略往往是成功的，特别是如果一个紧凑的配方存在。实际上，线性规划在理论和实践中都可以有效地求解。为了用凸规划或整数规划来表示问题，我们将可行解编码为高维空间中的点，使得待优化的函数可以表示为空间上的线性函数。然后，我们优化这些高维点的凸船体的线性函数。对于典型的组合问题，我们需要指数数量的线性不等式来描述凸船体。有时候没有这样的线性公式是已知的。令人惊讶的是，当我们引入额外的变量来编码原始问题中不明确的信息时，线性公式可能成为可能。此外，这样的扩展公式可能涉及更少的线性不等式，潜在地多项式很多。半正定公式，其中我们优化线性函数的半正定矩阵，提供了一个更强大的框架。特别是，扩展的半定公式可能比线性公式更紧凑。每当我们成功地获得一个紧凑的配方，我们可以借鉴现有的理论和软件，以提供有效的计算解决方案。在拟议的研究中，我计划研究的权力和限制的配方组合的问题，以及算法的基础上，这样的配方。我特别想探讨凸优化和组合优化的相互联系。通过这项研究，我们将获得基本优化问题的公式的理解。我们所建立的公式的强度和局限性对于设计这些问题的有效计算方法是非常重要的。例如，具有领带的稳定匹配问题属于所提出的研究计划的范围。任何新的见解，在制定这个问题可能会导致突破，近似最大基数稳定匹配。在目前的提案中，我们希望开发技术来解决这些和其他重要的悬而未决的问题的配方，收紧等领域的知识，如组合和连续优化理论，博弈论和图论之间的联系。

Combinatorial optimization is an important area of mathematical optimization. It captures many real-life problems. Familiar examples of such problems are developing road networks or matching users' requests with servers in an optimal way. One way to solve such problems is to develop combinatorial algorithms, but this approach is usually problem specific and not robust with respect to including additional constraints. Another way to approach such problems is to formulate them in terms of convex or integer programs. This allows us to draw from the rich theory of convex and integer programming. This strategy often turns out to be successful, especially if a compact formulation exists. Indeed, linear programs can be solved efficiently both in theory and in practice. To formulate a problem in terms of a convex or integer program we encode the feasible solutions as points in a high dimensional space, such that the function to be optimized can be expressed as a linear function on the space. We then optimize a linear function over the convex hull of these high dimensional points. For typical combinatorial problems we need an exponentially large number of linear inequalities to describe the convex hull. Sometimes no such linear formulation is known. Surprisingly, when we introduce additional variables that encode information not explicit in the original problem, linear formulation may become possible. Moreover such extended formulations may involve many fewer linear inequalities, potentially polynomially many. Positive semidefinite formulations, in which we optimize a linear function over positive semidefinite matrices, offer an even more powerful framework. In particular, extended semidefinite formulations may be even more compact compared to linear ones. Whenever we succeed in obtaining a compact formulation, we may draw on existing theory and software to provide efficient computational solutions. In the proposed research I plan to study the power and limitations of formulations of combinatorial problems, and the algorithms based on such formulations. I would especially like to explore the interconnections of convex and combinatorial optimization. Through this research, we will gain understanding of formulations for fundamental optimization problems. The strength and limitations of formulations that we establish are of tremendous importance for designing efficient computational methods for these problems. For example, the stable matching problem with ties belongs to the scope of the proposed research plan. Any new insights in formulations of this problem may lead to breakthroughs in approximating maximum cardinality stable matchings. In the current proposal we hope to develop techniques to settle these and other important open questions about formulations, tightening the connections between such areas of knowledge as theory of combinatorial and continuous optimization, game theory and graph theory.