Thursday, September 6 2018

11:00am - 12:15pm

11:00am - 12:15pm

Other Meetings and Presentations

Thesis Proposal, Charles Viss: Circuits in Optimization

The circuit directions of polyhedra play a fundamental role in the theory of optimization due to their connections to combinatorial algorithms and the efficiency of the Simplex method. Geometrically, circuits correspond to the potential edge directions of a polyhedron as its right-hand side varies. These directions can be used to traverse the vertices of a polyhedron in a manner that generalizes edge walks. We explore the behavior of these so-called circuit walks in various classes of polyhedra and show that circuit walks in many well-known polyhedra of discrete optimization yield intuitive combinatorial algorithms. Furthermore, the set of circuits of a polyhedron serves as an optimality certificate for any associated linear program and can therefore be employed in various optimization algorithms. However, this set of directions may be exponentially large, making such approaches computationally difficult. We propose new methods for computing the complete set of circuits of any polyhedron, regardless of representation, as well as computing certain subsets of circuits that satisfy desirable properties. Finally, we explore a circuit generalization of the combinatorial diameter of polyhedra. A major open question in optimization, pertaining to a polynomial pivot rule for the Simplex method, is whether or not the combinatorial diameter of a polyhedron can by polynomially bounded. The study of the so-called circuit diameter of polyhedra may provide insight into this difficult problem. We particularly consider the circuit and combinatorial diameters of polyhedra defined by totally unimodular matrices in relation to the famous Hirsch Conjecture.

Speaker: | Charles Viss |

Affiliation: | CU Denver |

Location: | SCB 4119 |

Done