Diagnosing Infeasibility in Min-cast Network Flow Problems Part I: Dual Infeasibility

One problem in modern large-scale model management is to provide computer assistance to help an analyst determine the cause of infeasibility when such is the case. This paper develops diagnostics for the special case of a mincost network flow problem, which is a richly structured subset of linear programming models. In this first of two parts, dual infeasibility is settled with a fundamental therorem whose constructive proof yields a polynomial algorithm to derive a substructure that the analyst can understand, giving a useful diagnostic display.