Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

University of Waterloo

$48,000.00

Optimization, matroids and graphs

FY 2022-23

Summary
Linear Programming and the advent of efficient algorithms marked the birth of the sprawling field of optimization. Most classes of optimization problems can be viewed as extensions of Linear Programs. For example, Integer Programs are obtained from Linear Programs by imposing the additional condition that some of the variables must take integer values. In some instances, this requirement is automatically satisfied (this happens when the set of feasible solutions form an integral polyhedron). For those instances Integer Programming reduces to Linear Programming. The study of Set Packing polyhedra that are integral leads to the theory of Perfect Graphs. In this proposal we will study Set Covering polyhedra that are integral. In other words, we wish to develop the analogue of the theory of Perfect Graphs, but for set covering polyhedra. Central to this project is a four decade-old conjecture by famed mathematician Paul Seymour on flowing matroids that can be viewed as the analogue to the Strong Perfect Graph Conjecture. I have proved multiple special cases of this conjecture and I am optimistic that the general conjecture is within reach. A number is dyadic if it has an exact binary expansion. A Dyadic Program is the optimization problem obtained from a Linear Program by imposing the additional condition that the variables must take dyadic values. Our goal is to develop a theory for Dyadic Programs. This theory will borrow features from both linear programming and integer programming theory. For instance, we recently proved that solving Dyadic Programs can be done in polynomial time (just like for Linear Programs), but that the support of an optimal solution can be large (just like for Integer Programs). For Integer Programs we asked, when is it that we get integrality for free (i.e., by solving the Linear Programming relaxation)? For Dyadic Programs we can also ask, when is it that we get a dyadic solution for free? A fascinating conjecture by Paul Seymour, predicts that this happens for Set Covering Polyhedra that are integral. Our proposed research on Dyadic Programs has direct relevance to this conjecture and to the Integer Programming community at large. Seymour's flowing conjecture on Set Covering polyhedra, can be expressed as a problem on binary matroids. Of relevance to this conjecture is a special class of binary matroids known as even-cycle matroids. Graphic matroids form a fundamental class of matroids, indeed, they appear in Whitney's 1935 foundational paper on matroids. Graphic matroids are very well understood with results of Tutte on recognition and excluded minors. Even-cycle matroids are binary lifts of graphic matroids and are probably the most natural extension of graphic matroids. In a breakthrough with a former PhD student, we were able to solve the recognition problem. In this proposal we plan to leverage the machinery that we already developed to find an excluded minor characterization.
Program
Discovery Grants Program - Individual
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
RGPIN-2022-03191
Name nom
Guenin, Bertrand
Department département
Combinatorics and Optimization - Combinatorics and Optimization
Organization id
33
Institution établissement
University of Waterloo
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2022
Competition year année de concours
2022
Award amount
48000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
1205
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Mathematical sciences
Area of application fr
Sciences mathématiques
Research subject code
2900
Research subject group en
Pure mathematics
Research subject group fr
Mathématiques pures
Research subject en
Pure mathematics
Research subject fr
Mathématiques pures
Installment
inst:1
Partie
1
Nb partie
5
Application title
Optimization, matroids and graphs
Application summary
Linear Programming and the advent of efficient algorithms marked the birth of the sprawling field of optimization. Most classes of optimization problems can be viewed as extensions of Linear Programs. For example, Integer Programs are obtained from Linear Programs by imposing the additional condition that some of the variables must take integer values. In some instances, this requirement is automatically satisfied (this happens when the set of feasible solutions form an integral polyhedron). For those instances Integer Programming reduces to Linear Programming. The study of Set Packing polyhedra that are integral leads to the theory of Perfect Graphs. In this proposal we will study Set Covering polyhedra that are integral. In other words, we wish to develop the analogue of the theory of Perfect Graphs, but for set covering polyhedra. Central to this project is a four decade-old conjecture by famed mathematician Paul Seymour on flowing matroids that can be viewed as the analogue to the Strong Perfect Graph Conjecture. I have proved multiple special cases of this conjecture and I am optimistic that the general conjecture is within reach. A number is dyadic if it has an exact binary expansion. A Dyadic Program is the optimization problem obtained from a Linear Program by imposing the additional condition that the variables must take dyadic values. Our goal is to develop a theory for Dyadic Programs. This theory will borrow features from both linear programming and integer programming theory. For instance, we recently proved that solving Dyadic Programs can be done in polynomial time (just like for Linear Programs), but that the support of an optimal solution can be large (just like for Integer Programs). For Integer Programs we asked, when is it that we get integrality for free (i.e., by solving the Linear Programming relaxation)? For Dyadic Programs we can also ask, when is it that we get a dyadic solution for free? A fascinating conjecture by Paul Seymour, predicts that this happens for Set Covering Polyhedra that are integral. Our proposed research on Dyadic Programs has direct relevance to this conjecture and to the Integer Programming community at large. Seymour's flowing conjecture on Set Covering polyhedra, can be expressed as a problem on binary matroids. Of relevance to this conjecture is a special class of binary matroids known as even-cycle matroids. Graphic matroids form a fundamental class of matroids, indeed, they appear in Whitney's 1935 foundational paper on matroids. Graphic matroids are very well understood with results of Tutte on recognition and excluded minors. Even-cycle matroids are binary lifts of graphic matroids and are probably the most natural extension of graphic matroids. In a breakthrough with a former PhD student, we were able to solve the recognition problem. In this proposal we plan to leverage the machinery that we already developed to find an excluded minor characterization.
University of Waterloo - $48,000 Grant (2022-23) | Canada Spends