Debugging infeasible models with an IIS

Debugging infeasible models with an IIS#

When solve() returns status == "infeasible", the model has no solution — but the full constraint list rarely tells you why: most constraints are innocent bystanders. An Irreducible Infeasible Subsystem (IIS) is a minimal set of constraints (and variable bounds) that is infeasible on its own, yet becomes feasible if any single member is removed [Chinneck, 2008]. It is the smallest self-contained explanation of the conflict — the analogue of Gurobi’s computeIIS and CPLEX’s conflict refiner.

The algorithm: deletion filtering#

discopt computes an IIS by deletion filtering [Chinneck and Dravnieks, 1991]:

  1. Confirm the full model is (provably) infeasible.

  2. Tentatively drop one candidate (a constraint or a finite variable bound) and re-solve a feasibility problem.

  3. If the remainder is still provably infeasible, the candidate is redundant to the conflict — drop it for good. If feasibility is restored, the candidate is essential — keep it.

  4. What survives is an IIS.

Soundness with an incomplete solver. A candidate is removed only when the reduced model is proven infeasible. A solve that is merely inconclusive (a nonconvex MINLP that times out without a proof) is conservatively treated as “keep the candidate”. The result is therefore always a genuine infeasible subsystem; it is irreducible exactly when every probe was conclusive — always the case for LP / MILP / convex models. IISResult.proven_irreducible reports which guarantee you have.

import discopt.modeling as dm

A constraint conflict hidden among red herrings#

Here x is pushed above 5 and below 2 — a contradiction — while two other constraints are perfectly satisfiable. solve() only reports infeasible; the IIS pinpoints the two constraints that actually clash.

m = dm.Model('blend')
x = m.continuous('x', lb=-10, ub=10)
y = m.continuous('y', lb=-10, ub=10)
m.subject_to(x >= 5, name='demand_floor')
m.subject_to(x <= 2, name='capacity_cap')
m.subject_to(y <= 3, name='side_limit')        # red herring
m.subject_to(x + y <= 8, name='budget')        # red herring
m.minimize(x + y)

res = m.solve()
print('solve status:', res.status)

solve status: infeasible

iis = m.compute_iis()
print(iis.summary())
print('\nfeasibility solves used:', iis.n_solves)

Irreducible Infeasible Subsystem (2 members):
  Constraints:
    - demand_floor:  (5 - x) <= 0
    - capacity_cap:  (x - 2) <= 0

feasibility solves used: 9

Out of four constraints, the IIS names exactly demand_floor and capacity_cap — the two you would edit to fix the model — and confirms the result is provably minimal.

Conflicts involving variable bounds#

Infeasibility is often driven by a bound, not a constraint. By default compute_iis also treats finite variable bounds as removable members, so it can surface a clash between a bound and a constraint. Here the lower bound x >= 5 fights the constraint x <= 2:

m2 = dm.Model('bound_conflict')
x2 = m2.continuous('x', lb=5, ub=10)   # the lower bound is the culprit
z = m2.continuous('z', lb=-1, ub=1)
m2.subject_to(x2 <= 2, name='cap')
m2.subject_to(z >= -0.5, name='unrelated')
m2.minimize(x2)

iis2 = m2.compute_iis()
print(iis2.summary())

Irreducible Infeasible Subsystem (2 members):
  Constraints:
    - cap:  (x - 2) <= 0
  Variable bounds:
    - x >= 5

/Users/jkitchin/projects/discopt/python/discopt/debug/__init__.py:98: UserWarning: Variables with very large or infinite declared bounds: x (lb=-1e+20, ub=1e+20), z (lb=-1, ub=1e+20). Nonlinear tightening can adjust 1 bounds via separable_quadratic_upper_bound. NLP solvers may fail (NaN, iteration_limit) when bounds exceed ~1e15. Add tighter explicit bounds, e.g. m.continuous('x', lb=0, ub=1000).
  return fn(*args, **kwargs)

The IIS reports both the constraint cap and the variable bound x >= 5, while ignoring the unrelated variable z. Pass include_bounds=False to restrict the IIS to explicit constraints only.

Integer-domain infeasibility#

Deletion filtering works for any class the solver can certify infeasible — including integrality. Requiring an integer strictly between 3 and 4 is infeasible, and the IIS isolates the two bracketing constraints:

m3 = dm.Model('integer_gap')
yv = m3.integer('y', lb=0, ub=10)
m3.subject_to(yv >= 3.2, name='lower')
m3.subject_to(yv <= 3.8, name='upper')
m3.minimize(yv)

print('status:', m3.solve().status)
print(m3.compute_iis(include_bounds=False).summary())

status: infeasible
Irreducible Infeasible Subsystem (2 members):
  Constraints:
    - lower:  (3.2 - y) <= 0
    - upper:  (y - 3.8) <= 0

Practical notes#

  • Cost. Deletion filtering performs up to one feasibility solve per candidate, so it scales with the number of constraints and finite bounds. Run it on demand (when a solve returns infeasible), not in the hot loop.

  • Reliability. Most precise on LP / MILP / convex models, where infeasibility is certifiable. On nonconvex MINLP a probe may time out without a proof; compute_iis then keeps the candidate and sets proven_irreducible = False, so the returned set stays a valid (if possibly non-minimal) infeasible subsystem [Chinneck, 2008].

  • Not unique. A model can have several IISes; compute_iis returns one.

Summary#

Model.compute_iis() turns an opaque infeasible verdict into a short, actionable list of the constraints and bounds that conflict — computed by sound deletion filtering [Chinneck and Dravnieks, 1991] on discopt’s own solver, with an explicit minimality guarantee.