• Gurobi Staff

Hi Saška,

You could try an approach like you suggesting, perhaps using indicator constraints would be best, but are you aware that Gurobi offers this functionality already?

The knowledge base article How do I determine why my model is infeasible? will be useful for you.

- Riley

Even with
model.Parameters.Presolve = 0
model.Parameters.IISMethod = 1
model.ComputeIIS()
and writing the .ilp to file
The result is not the smallest irreducible subsystem. For example I get 8 constraints instead of 5.

I found:
https://support.gurobi.com/hc/en-us/articles/360041448572-How-does-Gurobi-compute-the-IIS-for-infeasible-models-
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.

And there not any updates after Gurobi 9.5 that can find the smallest IIS?

I don't know how indicators constraints is going to help me with this.

• Gurobi Staff

Hi Saška,

Currently the latest version of Gurobi is v10, and it also cannot guarantee finding a minimum IIS.  I'm not aware of any solvers which do guarantee the minimum IIS.

The suggestion of the indicator constraints was proposing as a method of "turning constraints on or off".  This can be used to naively implement a brute force approach to calculate a minimum IIS like the example below.  Don't forget the IIS includes variable bounds, which is why the variable in the example (which are essentially binary variables) are defined as integer and bounds are provided as constraints.

import gurobipy as gpfrom gurobipy import GRBimport itertoolsimport numpy as npm = gp.Model()x = m.addVar(vtype=GRB.INTEGER)y = m.addVar(vtype=GRB.INTEGER)z = m.addVar(vtype=GRB.INTEGER)potential_constraints = [    x >= 0,    x <= 1,    y >= 0,    y <= 1,    z >= 0,    z <= 1,    x + y >= 2,    x + z >= 2,    z + y >= 2,    x + y + z <= 2,    x + 2*z <= 3,    x + y + z >= 0,]# an auxiliary variable for each constraintaux = m.addMVar(len(potential_constraints), vtype=GRB.BINARY)for a, c in zip(aux.tolist(),potential_constraints):    m.addConstr((a == 1) >> (c))  # indicator constraintsm.update()# loop through all subsets of constraints, from smaller subsets to largerfor arr in sorted(itertools.product([0, 1], repeat=len(potential_constraints)), key=lambda x:sum(x)):    m2 = m.copy()    m2.params.OutputFlag = 0    m2.addConstr(aux == np.array(arr))  # "turn the constraints on" that correspond to 1s in arr    m2.optimize()    if m2.Status == GRB.INFEASIBLE:        print("found minimal", np.nonzero(arr)[0])        break

You could perhaps use this approach in a smarter way.  For example if Gurobi computes an IIS of size 8, then start with looking for an IIS of size 7 by ensuring sum(arr) == 7.  If you don't find one of size 7 then you know the IIS of size 8 is the smallest.  If you find one of size 7 then repeat for sum(arr) == 6.

This approach is only practical for toy models though.  You will find the time taken for the above approach will grow exponentially as the model size grows.  I think the approach you first suggested will work for finding the maximum set of feasible constraints, but not the minimum set of constraints in an IIS.  If we could formulate the problem as a MILP then we would, but solving it is much harder than this.

- Riley

Removing constraints but staying infeasible, this won't result in minimal IIS.
Trying all combinations outside Gurobi is indeed a slow choice. Speed impact 2^n.

Is there any chance that this will be implemented and optimized in the near future?
It would then be an unique selling point.

• Gurobi Staff

Thank you for the feedback, Saska.  One thing I could potentially add is that right now we deliver a small IIS with high probability, due to the nature of how things are implemented. That is, if you have say 2 disjoint IIS, one of size 10 and the other 1,000, it is ~100 times more likely you will see the one of size 10 at the end.  However, no deterministic guarantees can be made.

Hope this helps.