Monday, November 9th, 2015 | 4pm-5pm | Burnside 1205 |

Simon Fraser University

Circuit-based pivoting and diameter

We discuss augmented pivoting algorithms, as recently featured by De Loera, Hemmecke and Lee. In these algorithms, in addition to the local edge directions used in the simplex method, a discrete set of additional directions are available. Some of these pass into the interior of the feasible region or of mid-dimensional faces. Once a direction is chosen, it is followed as far as feasibility allows. We focus on the case where the available directions are the circuits i.e. the support minimal solutions to the homogenization of the equations defining the feasible region. These can also be thought of as the potential edge directions of the system under varying right-hand sides of the equations. A necessary condition for the existence of high-quality pivoting algorithms is the existence of short paths between the vertices of the feasible region in the sense of using only a small number of these pivots and augmentations. This leads to the notion of the circuit diameter of a polyhedron P, which is number of pivots in the longest minimal path between any pair of vertices in P. The circuit diameter is an analogue of the combinatorial diameter of a polyhedron, which is the longest minimal path using only edge moves. Borgwardt, Finhold and Hemmecke investigated circuit diameter and showed that dual transportation polyhedra have a very low circuit diameter, lower than their combinatorial diameter. They asked if the Hirsch bound of f-d (the number of facets of the polyhedron minus its dimension) which was once conjectured as an upper bound on the combinatorial diameter, might hold for the combinatorial diameter. We show that some known non-Hirsch polyhedra, notably the Klee-Walkup polyhedron, are not counter-examples to this circuit Hirsch conjecture. This is joint work with Timothy Yusun.