Diagnosing infeasibility in min-cost network flow problems Part II; Primal 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 min-cost network flow problem, which is a richly structured subset of linear programming models. In this second of two parts, primal infeasibility is developed using specialized reductions and early works on flow augmenting paths. The goal is to obtain a minimal causal substructure, which is partially derived from max-flow labels on an augmented network.