Gurobi can compute an Irreducible Inconsistent Subset (IIS) of an infeasible model. An IIS is a minimal subset of constraints and variable bounds that, if isolated from the rest of the model, is still infeasible. However, if any single constraint or bound from this subsystem is removed, the resulting subsystem is feasible. This can be used to identify which constraints render the model infeasible and need to be relaxed to find a feasible solution.
The approach is based on this paper:
ORSA JOURNAL ON COMPUTING
Vol. 2, No. 1, 1990, DOI: 10.1287/ijoc.2.1.61
Identifying Minimally Infeasible Subsystems of Inequalities
John Gleeson, Jennifer Ryan
We can show that the dual Farkas proof generates an IIS. We add the variable bounds as constraints and consider the linear system
A x <= b
The paper shows that the support (indices corresponding to the nonzero values) of any vertex (or basis) of
A'y = 0
b'y <= -1
y >= 0
gives an IIS. Note that there are different approaches to compute an IIS, and, since Gurobi does not compute the IIS with minimal cardinality, there may exist an irreducible infeasible system smaller than what Gurobi reports.
Please sign in to leave a comment.