UNB/ CS/ David Bremner/ optimization seminar/ 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.