Grant: Discovery Grants Program - Individual
University of Ottawa
$34,000.00
Strengths and Limitations of Formulations for Combinatorial Optimization Problems.
FY 2020-21
Summary
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.
Program
Discovery Grants Program - Individual
Recipient
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
RGPIN-2020-04346
Name nom
Pashkovich, Kanstantsin
Department département
School of Computer Science and Electrical Engineering
Organization id
28
Institution établissement
University of Ottawa
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2020
Competition year année de concours
2020
Award amount
34000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
802
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Information systems and technology
Area of application fr
Systèmes d'information et technologie de l'information
Research subject code
2956
Research subject group en
Applied mathematics
Research subject group fr
Mathématiques appliquées
Research subject en
Optimisation and optimal control theory
Research subject fr
Optimisation et théories de commande optimale
Installment
inst:1-5
Partie
5
Nb partie
5
Application title
Strengths and Limitations of Formulations for Combinatorial Optimization Problems.
Keyword
NSERC
Application summary
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.