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.