Many problems in combinatorial optimization can be expressed as detecting total dual integrality (TDI) in a system of linear inequalities. One such case is the weak perfect graph theorem (WPGT) of Lovasz. I will present experimentally feasible tools for detecting TDI via secondary fans and Groebner bases of toric ideals. Fitting within this framework is a new, Groebner basis proof of the WPGT for chordal graphs. More generally, it fits in well with previous work of Chandrasekaran & Tamir and Sebo to give an explicit polyhedral strengthening of the WPGT.
This is joint work with Andras Sebo.