Skip to main content

Minimal constraints needed to prove the contradiction




  • Riley Clement
    Gurobi Staff 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

  • Saška Magdy
    First Comment
    First Question

    Even with
    model.Parameters.Presolve = 0
    model.Parameters.IISMethod = 1
    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: 
    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.

  • Riley Clement
    Gurobi Staff 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 gp
    from gurobipy import GRB
    import itertools
    import numpy as np

    m = 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 constraint
    aux = m.addMVar(len(potential_constraints), vtype=GRB.BINARY)
    for a, c in zip(aux.tolist(),potential_constraints):
      m.addConstr((a == 1) >> (c)) # indicator constraints


    # loop through all subsets of constraints, from smaller subsets to larger
    for 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
        if m2.Status == GRB.INFEASIBLE:
            print("found minimal", np.nonzero(arr)[0])

    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

  • Saška Magdy
    First Comment
    First Question

    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.

  • Yuriy Zinchenko
    Gurobi Staff 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.


Please sign in to leave a comment.