Gurobi can compute an Irreducible Inconsistent Subset (IIS) of an infeasible model. 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:

We can show that the dual Farkas proof actually generates an IIS. If we add the bounds into constraints and consider the linear system

A x <= b x free

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. There are different approaches to compute an IIS, and you should also keep in mind that Gurobi does not compute the IIS with minimal cardinality, so there may exist an irreducible infeasible system smaller than what Gurobi recovers.

## Comments

0 comments

Article is closed for comments.