IIS stands for “Irreducible Infeasible Subsystem”. There is no Wikipedia entry for it. I’ve been using the definition from a Gurobi article.
Let \( I_0 \) be a subset of constraints. \( I_0 \) is an IIS iff:
- \( I_0 \) is infeasible.
- Removing any single constraint (“or bound”) from \( I_0 \) makes it feasible.
(I’ve never thought about what the “or bound” part is doing.)
Property 1: an IIS does not consist of disjoint infeasible systems
Example: the following constraints do not comprise an IIS.
- \( a \leq 0 \)
- \( a \geq 1 \)
- \( b \leq 0 \)
- \( b \geq 1 \)
because removing one constraint, say \( a \leq 0 \), leaves the infeasibility on \( b \).
Another non-IIS:
- \( a \geq 1 \)
- \( b \geq 1 \)
- \( a + b \leq 0 \).
Removing \( a \geq 1 \) leaves the infeasibility on \( b \).
Property 2: removing a constraint in an IIS does not make the original system feasible.
\( I_0 \) is a collection of rows from \( A x \leq B \).
Example:
- \( a \geq 3 \)
- \( b \geq 3 \)
- \( a + b \leq 2 \).
\( \{ a \geq 3,\ a + b \leq 2 \} \) is an IIS. But removing \( a \geq 3 \) from the original system doesn’t make it feasible.
Property 3: an IIS may not be “minimal”.
By “minimal” here, I mean that a set of constraints has the smallest cardinality. The Gurobi article talks about this property a bit. Some articles that I’ve come across use “minimal” to mean irreducible. That is condonable, because “minimal” is the term that a widely-cited paper uses.
Example:
- \( a \geq 1 \)
- \( b \geq 1 \)
- \( a + b \geq 2 \).
- \( a + b \leq 1.5 \)
The two subsystems \( \{ a + b \geq 2,\ a + b \leq 1.5 \} \) and \( \{ a + b \geq 2,\ a \geq 1,\ b \geq 1 \} \) are, in some sense, infeasible in the same way. In this example, the former is the minimal IIS. In practice, you often don’t know which constraints in your model are linear combinations of other constraints, so I suppose minimality is a nice-to-have. For my own work, the IIS that Gurobi returns has been useful.
This stackexchange thread cites a paper that says finding the min-cardinality IIS is NP-hard, and is hard to approximate.
How solvers compute an IIS for another article.