optlens

Why is my LP or MILP model infeasible? How to find the conflicting constraints

Your solver says "infeasible": no plan satisfies every constraint at once. It doesn't say which constraints are to blame, and in a model with thousands of rows, reading them won't tell you either. This guide shows the standard method on a small model, with HiGHS and Gurobi, then the step most guides skip: turning the answer into a fix.

The model

A furniture maker plans one week. Two plants make chairs, tables and desks, and the contracts promise 120 chairs, 60 tables and 70 desks. The south plant is down for maintenance this week, so it has 150 hours instead of 300.

"""A week's furniture production plan, infeasible: the south plant is down for maintenance (150 hours instead of 300),
and the contracts still need 650 hours. The model behind the guides on optlens.dev."""
import pyomo.environ as pyo

PRODUCTS = {"chairs": 1, "tables": 3, "desks": 5}         # hours per unit
PROFIT = {"chairs": 20, "tables": 70, "desks": 130}
CONTRACT = {"chairs": 120, "tables": 60, "desks": 70}     # units promised to customers this week
MARKET = {"chairs": 300, "tables": 120, "desks": 100}     # most the market takes
HOURS = {"north": 400, "south": 150}                      # south: maintenance week
STORAGE = 400                                             # units the warehouse holds

m = pyo.ConcreteModel("furniture_week")
m.make = pyo.Var(PRODUCTS, HOURS, domain=pyo.NonNegativeReals)
m.make["desks", "south"].setub(0)                         # desks are made only in the north
m.profit = pyo.Objective(expr=sum(PROFIT[p] * m.make[p, k] for p in PRODUCTS for k in HOURS), sense=pyo.maximize)
m.capacity = pyo.Constraint(HOURS, rule=lambda m, k: sum(PRODUCTS[p] * m.make[p, k] for p in PRODUCTS) <= HOURS[k])
m.contract = pyo.Constraint(PRODUCTS, rule=lambda m, p: sum(m.make[p, k] for k in HOURS) >= CONTRACT[p])
m.market = pyo.Constraint(PRODUCTS, rule=lambda m, p: sum(m.make[p, k] for k in HOURS) <= MARKET[p])
m.storage = pyo.Constraint(expr=sum(m.make[p, k] for p in PRODUCTS for k in HOURS) <= STORAGE)

The solver says infeasible. The cause is simple arithmetic: the contracts need 120 × 1 + 60 × 3 + 70 × 5 = 650 hours, and the two plants have 400 + 150 = 550. In a real model you can't see that by reading. You find it with an IIS.

Step 1: find the IIS

An IIS (irreducible infeasible subsystem) is a set of constraints that can't hold together, and is minimal: drop any one and the rest can be satisfied. It's the part of the model you need to read. Everything outside it is innocent.

Write the model as an LP file so that any solver can read it:

from furniture_week import m

m.write("furniture_week.lp", io_options={"symbolic_solver_labels": True})

With HiGHS

HiGHS (free, open source) computes an IIS with getIis. Its default strategy can return an empty IIS, so ask for an irreducible one:

import highspy

h = highspy.Highs()
h.setOptionValue("output_flag", False)
h.readModel("furniture_week.lp")
# the default IIS strategy can return an empty IIS; ask for an irreducible one
h.setOptionValue("iis_strategy", int(highspy.IisStrategy.kIisStrategyIrreducible))
h.run()
status, iis = h.getIis()
lp = h.getLp()
for i in iis.row_index_:
    print(lp.row_names_[i])
c_u_capacity(north)_
c_u_capacity(south)_
c_l_contract(chairs)_
c_l_contract(desks)_
c_l_contract(tables)_

With Gurobi

import gurobipy as gp

with gp.Env(empty=True) as env:
    env.setParam("OutputFlag", 0)
    env.start()
    m = gp.read("furniture_week.lp", env)
    m.optimize()
    m.computeIIS()
    for c in m.getConstrs():
        if c.IISConstr:
            print(c.ConstrName, c.Sense, c.RHS)
c_u_capacity(north)_ < 400.0
c_u_capacity(south)_ < 150.0
c_l_contract(chairs)_ > 120.0
c_l_contract(desks)_ > 70.0
c_l_contract(tables)_ > 60.0

Both find the same five constraints: the two plants' hours and the three contracts. The market limits and the warehouse limit aren't in the IIS, so the problem isn't there.

Step 2: read the IIS as a business conflict

An IIS is a list of rows, not an explanation. Group it by what the constraints mean: here, the contracts ask for more than the capacity gives. The explanation for a planner is one sentence: "the contracts need 650 hours this week, and with the south plant in maintenance we have 550."

An IIS shows only one conflict. A model can have several. Fix this one, solve again, and check for the next.

Step 3: find the smallest fix

An IIS tells you what conflicts, not what to change. To find the least you have to change, solve a feasibility relaxation: let every constraint be broken, at a cost, and minimize the total amount broken. In Gurobi:

import gurobipy as gp

with gp.Env(empty=True) as env:
    env.setParam("OutputFlag", 0)
    env.start()
    m = gp.read("furniture_week.lp", env)
    m.feasRelaxS(0, False, False, True)  # least total violation, constraints only
    m.optimize()
    for v in m.getVars():
        if v.VarName.startswith("Art") and v.X > 1e-6:
            print(v.VarName, round(v.X, 6))
ArtP_c_l_contract(desks)_ 20.0

The cheapest fix is 20 fewer desks. That's the 100 missing hours at 5 hours a desk. But "cheapest" here depends on units: the relaxation compares hours of capacity with units of product as if they cost the same. Adding 100 hours to the south plant is a different fix, and it might be the one the business picks. Try each kind of fix, not just the first one the solver returns.

The same in one step with optlens

optlens is an open-source Python library that runs these steps on HiGHS (or SCIP, or your own Gurobi). It reads LP and MPS files and Pyomo, gurobipy and PuLP models. compute_iis groups the IIS by constraint family. fix_menu gives the smallest change in each family and solves the model with that change:

import optlens as od
from optlens.session import Session, Version

if __name__ == "__main__":  # optlens solves in worker processes
    md = od.load("furniture_week.py")
    s = Session({"v0": Version(md, None, "this week's plan")})
    print(s.compute_iis())
    print(s.fix_menu())
IIS (highs:irreducible): 5 constraints; by family: contract: 3, capacity: 2
capacity[north]: 1 make[chairs,north] +3 make[tables,north] +5 make[desks,north] <= 400
capacity[south]: 1 make[chairs,south] +3 make[tables,south] +5 make[desks,south] <= 150
contract[desks]: 1 make[desks,north] +1 make[desks,south] >= 70
contract[tables]: 1 make[tables,north] +1 make[tables,south] >= 60
contract[chairs]: 1 make[chairs,north] +1 make[chairs,south] >= 120
variable bounds in the IIS:
  make[chairs,north]: [0, inf]
  make[chairs,south]: [0, inf]
  make[tables,north]: [0, inf]
  make[tables,south]: [0, inf]
  make[desks,north]: [0, inf]
  make[desks,south]: [0, 0]
contract: sufficient; total change 20 over 1 bounds; best plan with it: objective 13100
    contract[desks]: RHS lower bound (>= side) 70 -> 50 (minimal change 20)
capacity: sufficient; total change 100 over 1 bounds; best plan with it: objective 15700
    capacity[south]: RHS upper bound (<= side) 150 -> 250 (minimal change 100)
(all families together: unrestricted minimum): sufficient; total change 20 over 1 bounds; best plan with it: objective 13100
    contract[desks]: RHS lower bound (>= side) 70 -> 50 (minimal change 20)
suggested values are the exact minimum; copy them exactly as printed (a rounded boundary value can land on the infeasible side)

Two fixes, each solved: cut the desk contract from 70 to 50 (profit 13,100), or give the south plant 250 hours (profit 15,700). Which one is right is a business decision, but now both have a number.

Common causes

Run with optlens 0.0.3, Pyomo 6.10.1, HiGHS (highspy) 1.15.1 and gurobipy 13.0.3.

← Back to optlens