optlens

Why is my MILP infeasible? A proof you can check, on a hotel week

When a solver reports an infeasible model, an IIS lists the constraints that conflict. It does not say why they conflict, and on a large model the reason can involve rules far from the one you were looking at. The solver has already computed that reason: weights for the conflicting rows that, added up, give a contradiction. This guide shows that proof on a hotel planning MILP.

The model

The hotel week from the optlens hotel pack: one hotel, 14 nights, 2,691 rows and 2,520 integer variables (bookings by room type, stay length, booking window and rate tier). Its document lists the business rules: room capacity, forecast demand, discount caps, a brand-standard occupancy floor, a group-wide occupancy floor, and a housekeeping team that turns over at most 110 rooms a day. One number was typed wrong during a data load, and the model is infeasible.

The proof

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

if __name__ == "__main__":  # optlens solves in worker processes
    s = Session({"v0": Version(od.load("hotel_week.lp.gz"), None, "the week as loaded")})
    print(s.compute_iis().splitlines()[1])  # the IIS's size and families
    print(s.infeasibility_proof())
IIS (lp_relaxation:highs:irreducible): 4 constraints; by family: housekeeping: 3, group_occupancy: 1
no plan meets these 4 rows at once (the IIS; exact for this MIP: the conflict holds even with fractional values):
  require at least 1200:
    group_occupancy (1 row): 1200   [group_occupancy(d5) >= 1200]
  allow at most 330:
    housekeeping (3 rows): 330   [housekeeping(h1_d6) <= 110; housekeeping(h1_d7) <= 110; housekeeping(h1_d8) <= 110]
short by 870: each row is weighted as shown (weights make the rows' left-hand sides add up to the same quantity), and the sums are checked by arithmetic
requiredgroup_occupancy: 1 row, 1,200group_occupancy (1)1,200allowedhousekeeping: 3 rows, 330330 housekeeping (3)
The proof to scale: the families on each side and their totals. Short by 870.

The IIS has four rows: the group occupancy floor for night 5, and the housekeeping limits for the mornings of nights 6, 7 and 8. Every weight is 1. The floor requires at least 1,200 rooms in house on night 5. The three housekeeping limits allow at most 3 × 110 = 330.

This output comes from the solver and optlens alone, with no language model involved. HiGHS finds the IIS and the weights; optlens adds the weighted rows to check the contradiction, groups the rows by name and prints the result. The same model always gives the same output, and you can redo the sum by hand. The next section is different: it explains the rows in the hotel's terms, which takes the model's document and some judgement. In the optlens plugin, the agent writes that part; here we wrote it and checked it against the document.

In the hotel's terms

Stays last at most three nights, so every guest in house on night 5 checks out on the morning of night 6, 7 or 8. Each check-out is a room housekeeping has to turn over, and housekeeping can turn over at most 110 rooms a morning. That allows at most 330 check-outs over those three mornings, so at most 330 rooms can be occupied on night 5. A floor of 1,200 cannot be met.

The IIS names the four rows but not this chain of reasoning; the weighted sum makes it visible. The document sets the group floor at 60 % of the group's 200 rooms, which is 120. The value 1,200 has an extra zero. With 120 restored, the week solves:

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

if __name__ == "__main__":
    s = Session({"v0": Version(od.load("hotel_week.lp.gz"), None, "the week as loaded")})
    print(s.modify_and_resolve("v0", "night 5's group floor back to 120",
                               [{"action": "set_rhs", "name": "group_occupancy(d5)", "lower": 120}]).splitlines()[0])
created v1 from v0 (1 changes): status OPTIMAL

When this works for a MILP

The proof is a weighted sum of rows, so it is a statement about the LP relaxation: the same model with integer variables allowed to take fractional values. In this week the conflict exists even with fractional values, because no plan of any kind reaches 1,200. The proof therefore holds for the MILP as well, and the output says so. Of the 246 infeasible models in our benchmark, 237 have a proof of this kind, including every MILP whose relaxation is infeasible. The other 9 are MILPs that are infeasible only because the variables must be whole numbers, for example a team size of 3 that cannot divide 4 people. No single weighted sum proves those; the tool reports that, and the IIS remains the place to look.

Try it

The week and five planner questions are in the optlens repository. With the Claude Code plugin, ask why the week is infeasible, then ask for proof: the agent calls infeasibility_proof when you ask for proof or for the numbers, and explains the sum in the hotel's terms. In Python, od.certificate(model) returns the proof, checked by arithmetic.

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

← Back to optlens