Optimization, matroids and graphs

线性规划和高效算法的出现标志着庞大的优化领域的诞生。大多数优化问题都可以看作是线性规划的扩展。例如，线性规划是从线性规划中得到的，通过施加一些变量必须取整数值的附加条件。 在某些情况下，这个要求会自动满足（当可行解的集合形成一个整数多面体时会发生这种情况）。在这些情况下，可编程性可归结为线性规划。对集积多面体的研究导致了完美图理论。在这个建议中，我们将研究集覆盖多面体是完整的。换句话说，我们希望发展完美图理论的类似物，但对于集合覆盖多面体。这个项目的核心是著名数学家保罗·西摩（Paul Seymour）关于流动拟阵的一个四十年前的猜想，它可以被视为强完美图猜想的类似物。我已经证明了这个猜想的多个特殊情况，我乐观地认为，一般的猜想是触手可及的。一个数是二进的，如果它有一个精确的二进制扩展。二元规划是从线性规划中通过施加变量必须取二元值的附加条件而获得的优化问题。我们的目标是开发一个理论的二元程序。该理论将借用线性规划和整数规划理论的特征。例如，我们最近证明了求解二元规划可以在多项式时间内完成（就像线性规划一样），但是最优解的支持可以很大（就像线性规划一样）。对于可编程程序，我们问，什么时候我们可以免费获得完整性（即，解线性规划松弛法（Linear Programming Relax）对于二元程序，我们也可以问，什么时候我们可以免费得到一个二元解？保罗·西摩（Paul Seymour）提出的一个有趣的猜想预测，这种情况会发生在集覆盖多面体上。我们提出的研究二元程序有直接关系到这个猜想，并在广大的编程社区。Seymour关于集合覆盖多面体的流动猜想可以表示为二元拟阵的问题。与这个猜想相关的是一类特殊的二元拟阵，称为偶圈拟阵。图形拟阵形成了拟阵的一个基本类，事实上，它们出现在惠特尼1935年关于拟阵的基础论文中。图拟阵是非常好的理解与Tutte的识别和排除未成年人的结果。偶圈拟阵是图拟阵的二进制提升，可能是图拟阵最自然的扩展。在与一位前博士生的突破中，我们能够解决识别问题。在本提案中，我们计划利用我们已经开发的机制来找到排除的次要特征。

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.