How to Analyze the Results of Linear Programs—Part 3: Infeasibility Diagnosis

One problem in debugging a linear program is finding a way to diagnose an infeasible instance. The sources of error could be structural, such as inadvertent omission of activities, or data related, such as insufficient supply to meet demand. I present techniques that LP experts have used in practice for a variety of applications. It is important, however, to distinguish a diagnosis from an isolation. An isolation is a portion of the linear program obtained in some purposeful way to contain a probable cause. A diagnosis additionally requires an explanation of an isolation, which can require complex reasoning.