Title:A computational approach to the Hirsch Conjecture

The Hirsch conjecture is a 50 year old conjecture related to the worst case performance of the simplex method of Linear Programming. In this talk I will discuss recent work with Lars Schewe, and not so recent work with Fred Holt and Victor Klee, on a computational attack on this conjecture. The main tools are a (partial) classification of the simplicial complexes whose dual graph is a path, oriented matroids, and fast boolean satifiability solvers. Time permitting, I will compare the performance of a branch-and-cut based integer programming approach to a sat solver on these problems. Joint work with Lars Schewe, TU Darmstadt