The Hirsch Conjecture for Totally-Unimodular Polyhedra
Abstract
Many network, transportation, and clustering applications can be modeled as high-dimensional polyhedra defined by a totally-unimodular (TU) constraint matrix. The geometric properties of these objects encode valuable information of the underlying application. Studies of the graphs of polyhedra, and their combinatorial diameters, are a classical field in optimization motivated by their connection to the efficiency of linear programming. TU polyhedra are the arguably most important class of polyhedra in integer programming for which the bound given in the famous, but disproved Hirsch Conjecture - a bound of f-d for the diameter of all d-dimensional polyhedra with f facets – remains open. Our main goal is to prove the Hirsch Conjecture for all TU polyhedra. Our methods combine polyhedral theory, diameter studies, matroid theory, and augmentation algorithms, to establish a new approach to this long-standing problem. A powerful tool is a new interpretation of Seymour's decomposition theorem, giving a set of rules for the explicit construction of all TU matrices from basic network matrices. We are going to study the diameters for network matrices and the impact of each rule on the diameter. A best-possible outcome of this project is a complete proof for all TU polyhedra, achieved by showing that all network matrix polyhedra satisfy the conjecture, and that all rules keep this validity. Each step towards this result will advance the state of the art: unlike classical research on the topic, we construct edge walks explicitly and efficiently, which will have profound algorithmic implications. We investigate these benefits to further algorithmic practice, ranging from generalizations of the network simplex algorithm over a new perspective on column generation and row decomposition strategies, to direct applications for explicit edge walks in network applications.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Jan 21, 2022
- Source ID
- FA95502110233XX0
Entities
People
- Steffen Borgwardt
Organizations
- Air Force Office of Scientific Research
- Regents of the University of Colorado
- United States Air Force