Integral infeasibility and testing total dual integrality

A number of well known results in combinatorial optimization, such as Hoffman’s circulation theorem and the matching theorems of Hall and Tutte, can be interpreted as stating that either a certain linear system has a solution or there exists a simple combinatorial reason why it is infeasible. The authors give a characterization of total dual integrality in terms of such infeasibility results. This leads to a method for testing total dual integrality which is tractable for small linear systems. In particular, a computer implementation of the method settled a conjecture of Barahona and Mahjoub concerning feedback sets in directed graphs.