AF: Small: Circuit Walks in Optimization

University Of Colorado At Denver-Downtown Campus, Denver CO

Investigators

Abstract

The field of optimization provides powerful tools for finding optimal solutions to mathematical programs based on complex real-world problems. However, the computation of a better solution is just a first step towards the greater goal of actually implementing it in practice. In many applications, a gradual transition to a new transportation plan, a new schedule, a new database structure, or a new software solution is required. Such a transition should be a short sequence of simple and natural steps that satisfy a combination of optimality criteria and restrictions associated with the problem. The goal of this project is the design, study, and implementation of algorithms for optimal gradual transitions between solutions of a mathematical program. The ability to efficiently construct such a transition will enable a wealth of new applications. The project will raise awareness in the scientific community to go beyond just solving a problem and will advance knowledge on the transfer of computational results to practice. The research is complemented with synergistic education and outreach activities, including new courses, the training of students, and a workshop bringing together students from across the country with international experts. The impact will be tested in applications, involving students through a collaboration with the Auraria Library's Data to Policy Project. For the polyhedra arising in linear and integer programming, a transition between two solutions can be modeled as a walk along the so-called circuits, the elementary, support-minimal difference vectors retaining feasibility. The circuits contain valuable information on the underlying application. Each step of a circuit walk is a meaningful, human-interpretable step towards the new solution. This project aims to provide a broad, comprehensive approach to the efficient construction of optimal circuit walks in various settings. The main settings are circuit walks between two given solutions, motivated by the need for gradual transitions in practice. Further, circuit walks are a generalization of edge walks, and the corresponding circuit diameters provide a fresh point of view on the polynomial Hirsch Conjecture. Finally, augmentation along circuits is a generalization of the famous simplex method and gives a new way to deal with degenerate polyhedra and to study the existence of a polynomial pivot rule. The methods will combine applied graph theory, polyhedral theory, mathematical programming, and complexity theory. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.