Optimization, matroids and graphs

点击翻译按钮获取中文摘要

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.