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.