Monday, April 6 2020
11:00am - 12:45pm
PhD Thesis Presentation,Operations Research Seminar
Circuits in Optimization

Circuits play a fundamental role in the theory of linear programming due to their intimate connection to algorithms of combinatorial optimization and the efficiency of the simplex method. Generalizing edge walks, circuit walks follow the edge directions of the underlying polyhedron and often have useful combinatorial interpretations. Further, circuits are used as step directions in various augmentation schemes for solving linear programs. We are interested in better understanding the properties of circuit walks in polyhedra as well as working toward viable implementations of circuit augmentation schemes.

We first introduce a hierarchy for integral polyhedra based on different types of behavior exhibited by their circuit walks. Second, we relate circuits to a fundamental task in data analytics and machine learning: the clustering of large data sets. In particular, we consider an application in which one clustering is gradually transformed into another via circuit walks. Third, we address significant challenges regarding the computation of circuits via a proposed polyhedral model. This model serves as a universal framework for representing the set of circuits of any polyhedron and enables the efficient computation of so-called steepest-descent circuits. Lastly, we work toward a viable implementation of a steepest-descent circuit augmentation scheme in which our dynamic model provides the required augmenting directions.
Speaker:Charles Viss
Affiliation:University of Colorado Denver
Location:See Zoom link from email

Download as iCalendar