Note--Post-Infeasibility Analysis in Linear Programming

When a linear programming problem is found to have no feasible solution, the model-builder generally has no tools for systematically determining why the infeasibility exists and what might be done to eliminate it. The assumption is made, at least implicitly, that if the model has no feasible solution, it is wrong to some fundamental way and must be corrected before it can be of use to the model-builder. In fact, the model may be quite correct as it stands, in the sense that it captures exactly what the model-builder meant for it to capture. When this is the case, discovering the absence of a feasible solution can be useful to the model-builder, and correspondingly, tools for exploring the nature of the infeasiblity can be quite valuable. The purpose of this paper is to develop a set of methods for doing post-infeasibility analysis on linear programming problems. The methods are designed to identify constraints that might be "relaxed" to attain feasibility and estimate the magnitudes of the required changes.