Infeasibility AnalysisΒΆ
The optimization model is not ways feasible, and the optimizer may tell us some information about the infeasibility to diagnose the problem. There are two ways to handle the infeasibilities:
Find the IIS (Irreducible Infeasible Set) to identify the minimal set of constraints that cause the infeasibility.
Relax the constraints and solve a weaker problem to find out which constraints are violated and how much.
PyOptInterface currently supports the first method to find the IIS (only with Gurobi and COPT). The following code snippet shows how to find the IIS of an infeasible model:
import pyoptinterface as poi
from pyoptinterface import copt
model = copt.Model()
x = model.add_variable(lb=0.0, name="x")
y = model.add_variable(lb=0.0, name="y")
con1 = model.add_linear_constraint(x + y, poi.Geq, 5.0)
con2 = model.add_linear_constraint(x + 2 * y, poi.Leq, 1.0)
model.set_objective(x)
model.computeIIS()
con1_iis = model.get_constraint_attribute(con1, poi.ConstraintAttribute.IIS)
con2_iis = model.get_constraint_attribute(con2, poi.ConstraintAttribute.IIS)
print(f"Constraint 1 IIS: {con1_iis}")
print(f"Constraint 2 IIS: {con2_iis}")
Constraint 1 IIS: True2025-01-27 09:13:06 [INFO] checks license for COPT v7.2.4 20241206
2025-01-27 09:13:06 [WARN] no license files in current working folder: /home/runner/work/PyOptInterface/PyOptInterface/docs/source
2025-01-27 09:13:06 [WARN] no license files in binary folder: /opt/hostedtoolcache/Python/3.12.8/x64/bin
2025-01-27 09:13:06 [WARN] no license files in HOME folder: /home/runner/copt
2025-01-27 09:13:06 [INFO] empty environment variable: COPT_LICENSE_DIR
2025-01-27 09:13:06 [WARN] no license files in EV 'COPT_LICENSE_DIR':
No license found. Starting COPT with size limitations for non-commercial use
Please apply for a license from www.shanshu.ai/copt
Constraint 2 IIS: True
No license found. LP size is limited to 10000 variables and 10000 constraints
Please apply for a license from www.shanshu.ai/copt
Model fingerprint: 43b22f9c
Start the IIS computation for an LP
Iteration Min RowBnd Max RowBnd Min ColBnd Max ColBnd Time
0 0 2 0 2 0.00s
2 0 2 0 2 0.00s
3 1 2 0 2 0.00s
4 2 2 0 2 0.00s
5 2 2 0 1 0.00s
6 2 2 0 0 0.00s
IIS summary: 2 rows, 0 bounds of columns
IIS computation finished (0.001s)
This code snippet creates an infeasible model with two constraints and finds the IIS of the model. Obviously, the constraints are contradictory because x + 2 * y <= 1 and x + y >= 5 cannot be satisfied at the same time when x and y are non-negative. The optimizer will detect that the model is infeasible and return the IIS, which is the set of constraints that cause the infeasibility. We can query whether a constraint is in the IIS by calling get_constraint_attribute with the ConstraintAttribute.IIS attribute.
Sometimes, the bounds of the variables are not consistent with the constraints, and we need to query the IIS of the bounds of variables by calling get_variable_attribute with the VariableAttribute.IISLowerBound and VariableAttribute.IISUpperBound attributes.
The following code snippet shows how to tell if the bounds of a variable are in the IIS:
model = copt.Model()
x = model.add_variable(lb=0.0, ub=2.0, name="x")
y = model.add_variable(lb=0.0, ub=3.0, name="y")
con1 = model.add_linear_constraint(x + y, poi.Geq, 6.0)
model.set_objective(x)
model.computeIIS()
con1_iis = model.get_constraint_attribute(con1, poi.ConstraintAttribute.IIS)
x_lb_iis = model.get_variable_attribute(x, poi.VariableAttribute.IISLowerBound)
x_ub_iis = model.get_variable_attribute(x, poi.VariableAttribute.IISUpperBound)
y_lb_iis = model.get_variable_attribute(y, poi.VariableAttribute.IISLowerBound)
y_ub_iis = model.get_variable_attribute(y, poi.VariableAttribute.IISUpperBound)
print(f"Constraint 1 IIS: {con1_iis}")
print(f"Variable x lower bound IIS: {x_lb_iis}")
print(f"Variable x upper bound IIS: {x_ub_iis}")
print(f"Variable y lower bound IIS: {y_lb_iis}")
print(f"Variable y upper bound IIS: {y_ub_iis}")
Constraint 1 IIS: True
Variable x lower bound IIS: False
Variable x upper bound IIS: True
Variable y lower bound IIS: False
Variable y upper bound IIS: True
No license found. LP size is limited to 10000 variables and 10000 constraints
Please apply for a license from www.shanshu.ai/copt
Model fingerprint: 6e53fbd7
Start the IIS computation for an LP
Iteration Min RowBnd Max RowBnd Min ColBnd Max ColBnd Time
0 0 1 0 2 0.00s
1 0 1 0 2 0.00s
2 1 1 0 2 0.00s
3 1 1 1 2 0.00s
4 1 1 2 2 0.00s
IIS summary: 1 rows, 2 bounds of columns
IIS computation finished (0.001s)