Localizing and diagnosing infeasibilities in networks

Network models are among the largest linear programs solved, but formulation can be a bottleneck. Errors may be introduced during formulation, reformulation, or when combining several smaller models into one large model (as is often done in econometrics). Simply knowing that the model is infeasible is not enough: where there are many nodes and arcs, the modeler needs guidance as to where repairs are needed (localization), and some indication of the cause of the error (diagnosis). The state of the art flow balancing methods for analyzing infeasible networks simply do not provide enough localization or diagnosis, and in addition cannot operate on advanced netforms. The paper presents an infeasiblity analysis procedure for all classes of network models that localizes the error to a minimal causative set of nodes, arcs, and constraints, and provides a basic diagnosis. The procedure builds on previous work but tunes the methods for the special case of networks. Examples are given, using solutions provided by PROFLOW, software for the formulation, analysis and solution of network models.