Advances in Circuit Augmentation
Abstract
Linear programming algorithms are a key tool for network problems that are too complex to solve with combinatorial algorithms. A primal Simplex method finds an optimal solution by tracing an augmenting edge walk in the underlying polyhedron. We study circuit augmentation schemes, which are a direct generalization by following steps along the more general set of circuits, tracing a walk through the interior of the polyhedron. Circuit augmentation can be seen as the transfer of the idea of cycle canceling to general linear programming. Circuits are the vectors corresponding to minimal dependence relations of a constraint matrix. In network applications, they typically correspond to cycles, paths, or cut sets. For the Simplex method, decades of refinement and improvements have gone into commercial solvers. For circuit augmentation schemes, many theoretical advances arose in the last decade and their practical potential remains largely untapped. The main project goal is the design, analysis, and better implementations of circuit augmentation schemes. A powerful tool to this end is a modeling technique that uses the original input to set up a polyhedron in which all circuits appear as vertices, so that efficient optimization over the set of circuits is possible without enumeration. We are going to study improvements to key challenges for current algorithms, such as the efficient computation of an initial feasible circuit and strategies that marry Simplex and circuit augmentation tools in a hybrid setting for more efficient iterations and early termination. Additionally, we will explore parallel computations and exact arithmetic algorithms. We are aiming for major improvements in the performance of circuit augmentation for general problems, and the identification of special settings in which these improvements and tailored refinements lead to an outperformance versus classical methods. The research will be disseminated in a series of journal papers and conference talks and software will be made publicly available.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Feb 06, 2025
- Source ID
- FA95502410240
Entities
People
- Steffen Borgwardt
Organizations
- Air Force Office of Scientific Research
- Regents of the University of Colorado
- United States Air Force