Why is My Model Infeasible?

A frequently asked question on various optimization mailing lists and web forums runs something like this: The solver says my <linear/integer/nonlinear/integer linear/integer nonlinear> optimization model is infeasible -- which constraint is causing it? The easy but unhelpful answer is that no one constraint causes a model to be infeasible.

Infeasibility is the result of a conflict among two or more constraints. It is important to note that "constraint" encompasses three types of restrictions: functional constraints (equations and inequalities involving two or more variables); lower and upper bounds on individual variables (including nonnegativity restrictions); and integrality requirements for individual variables. In all cases of infeasibility, the objective function is irrelevant; only constraints (as just defined) matter.

For linear programs, the acronym to know is IIS, which is sometimes expanded as Irreducible Infeasible Subset and sometimes as Irreducible Inconsistent Subsystem (as, for instance, in the Mathematical Programming Glossary). Either way, it means the same thing: a subset of the constraints and variable bounds that cannot be simultaneously satisfied (even if all other constraints/bounds are ignored), but such that removal of any one member of the IIS leaves you able to satisfy the remaining constraints/bounds in that IIS. That last qualification is important: there can be more than one IIS in a model, so removing (or sufficiently loosening) one of the members of a particular IIS may not be enough to make the model feasible.

There has been considerable research on efficient ways to identify IISes (but apparently no research on the correct way to write the plural of IIS), and on how to identify a minimal set of constraints/bounds whose removal will break all IISes and make the problem feasible. I believe the latter problem has been shown to be NP-hard. Having identified an IIS, it is not typically necessary to remove a constraint/bound entirely; relaxing one (or more) constraints/bounds sufficiently should do the trick. Contemporary LP solvers usually provide mechanisms for identifying at least one IIS, so all else failing you can repeatedly solve the model, identifying and correcting an IIS each time, until the model becomes feasible. (This may not be the route to feasibility that involves minimal amounts of relaxation, however.)

Which constraint(s) in an IIS to relax, and how much to relax them, is context specific. One possible approach is to insert a nonnegative variable into those constraints in the IIS (including bounds) that can possibly be relaxed. The new variables represent the amount of relaxation of the corresponding constraints. Add a penalty term to the objective for each of the added variables, assigning costs for the relaxations in a manner that makes sense in context. Then optimize the expanded model to find both an optimal solution and the "cheapest" combination of relaxations. Something similar should work for nonlinear programs, although I don't know if NLP solvers implement IIS finding routines.

When there are integrality restrictions, the picture gets more complicated. The first step is to relax the integrality restrictions and test whether the relaxed problem is feasible. If not, identify an IIS (or multiple IISes) and proceed as above. If the continuous relaxation if feasible, then the issue is that the feasible region of the relaxation does not contain any integer points. The only way I know to fix the model is to introduce the relaxation variables (and costs) I described above.