Finding a useful subset of constraints for analysis in an infeasible linear program

Infeasibility is often encountered during the process of intial model formulation or reformulation, and it can be extremely difficult to diagnose the cause, especially in large linear programs. While explanation of the error is the domain of humans or artificially intelligent assistants, algorithmic assistance is available to isolate the infeasibility to a subset of the constraints, which helps speed the diagnosis. The isolation should be infeasible, of course, and should not contain any constraints which do not contribute to the infeasibility. Algorithms for finding such irreducible inconsistent systems (IISs) of constraints have been proposed, implemented, and tested in recent years. Experience with IISs shows that a further property of the isolation is highly desirable for easing diagnosis: the isolation should contain as few model rows as possible. This article addresses the problem of finding IISs having few rows in infeasible linear programs. Theory is developed, then implemented and tested on a range of problems using a modified version of MINOS 5.4 called MINOS(IIS).