Gurobi's 'compute IIS' feature is designed to address the query: "What subset of model constraints is responsible for making the model infeasible?" In this article, we will show how to use this feature. A related article How do I determine why my model is infeasible? expands on the topic of infeasibility analysis tools further.
The 'compute IIS' feature identifies a irreducible set of conflicting constraints and limits within a model. Analyzing the entire set of constraints and variable bounds to pinpoint the cause of an infeasible model can be a daunting task. Gurobi's 'compute IIS' tools can reduce the problem to a possibly much smaller subset of conflicting constraints and limits, making it more manageable to comprehend and analyze.
An Irreducible Infeasible Subsystem (IIS) refers to a specific subset of constraints and variable bounds within an infeasible system. This subset satisfies two essential conditions: (a) it is itself infeasible, and (b) removing any single constraint or bound from the subset would result in a feasible subsystem. It is crucial to note that an IIS may not be the smallest infeasible subset (with respect to cardinality). More specifically, this means that an infeasible model may have multiple IISs, and the one returned by Gurobi might not necessarily be the one with the fewest constraints or bounds. Note that the algorithm we implement favors recovery of smaller IIS in general.
The 'compute IIS' results are designed to be examined and analyzed by human users, providing a starting point for understanding the problematic constraints in the model. The smaller the IIS, the more effectively it can pinpoint the specific issues in the model.
In terms of computational complexity, calculating an IIS is relatively inexpensive for linear programming (LP) problems, but is more computationally expensive for mixed-integer programming (MIP) problems.
Practical Usage Guide
In Python, you can compute an IIS using the Model.computeIIS() method. This can help you narrow down your list of suspicious constraints. After building and then solving the model, you can compute the IIS with the following:
import gurobipy as gp
from gurobipy import GRB
# Build the model
[...]
# Optimize
model.optimize()
# do IIS if the model is infeasible
if model.Status == GRB.INFEASIBLE:
model.computeIIS()
To get the results of this IIS, you can save the ILP file using:
model.write('iismodel.ilp')
Alternatively, you can query the IIS attributes for each constraint and variable using IISConstr, IISLB, IISUB, IISSOS, IISQConstr, and IISGenConstr. Each indicates whether the corresponding model element is a member of the computed IIS. Here is an example of printing out the variable limits and linear constraints in the IIS:
# Print out the IIS constraints and variables
print('\nThe following constraints and variables are in the IIS:')
for c in model.getConstrs():
if c.IISConstr: print(f'\t{c.constrname}: {model.getRow(c)} {c.Sense} {c.RHS}')
for v in model.getVars():
if v.IISLB: print(f'\t{v.varname} ≥ {v.LB}')
if v.IISUB: print(f'\t{v.varname} ≤ {v.UB}')
You can customize the use of this method by ignoring or forcing elements into the IIS using the ISConstrForce, IISLBForce, IISUBForce, IISSOSForce, IISQConstrForce, and IISGenConstrForce attributes.
Example usage
You can review an example of Compute IIS in action with the workforce1 example (C, C++, C#, Java, MATLAB, Python, R, VB). If you store the ILP file, it will return the following IIS
\ Model assignment_copy
\ LP format - for model browsing. Use MPS format to capture full model detail.
Minimize
Subject To
Thu4: x[Cathy,Thu4] + x[Ed,Thu4] = 4
Bounds
-infinity <= x[Cathy,Thu4] <= 1
-infinity <= x[Ed,Thu4] <= 1
End
This shows that the two variable upper limits of 1 on x[Cathy,Thu4] and x[Ed,Thu4] are inconsistent, with their sum being constrained to 4. The sum of these two variables can be at most 2. This is why these three constraints are contradictory. However, the model can be feasible if either of these upper bounds or this constraint is removed.
Comments
0 comments
Article is closed for comments.