Infeasibility Is a Business Signal

An infeasible optimization model is often treated like a software bug.

The solver returns INFEASIBLE, somebody opens the model code, and the team starts hunting for the constraint that must be wrong.

Sometimes there is a bug. Often there is not.

In production planning, infeasibility can be the most accurate answer the model has produced all week. It is telling you that the promises, limits, inventory, capacity, timing, and business rules you supplied cannot all be true at the same time.

That is not a solver failure. That is information.

The practical question is not simply “How do I make the model feasible?” It is “Which commitments conflict, what would have to change, and what is the economic consequence of changing it?”

That distinction matters because blindly restoring feasibility is easy. Restoring feasibility in a way that represents the business is the actual modeling problem.

Start With the Decision, Not the Error Message

Suppose you are building a weekly supply allocation model. You decide how much product to ship from distribution centers to customers:

[ x_{ijt} = \text{units shipped from location } i \text{ to customer } j \text{ in week } t. ]

The model includes available inventory, inbound supply, warehouse capacity, transportation capacity, customer commitments, allocation rules, minimum shipment quantities, product compatibility, and perhaps contractual service requirements.

The objective might minimize shortage and logistics cost:

[ \min \sum_{j,t} p_j s_{jt} + \sum_{i,j,t} c_{ij}x_{ijt}, ]

where (s_{jt}) is unmet demand and (p_j) is its economic penalty.

Now imagine the business says Customer A must receive at least 10,000 units this week, Customer B must receive at least 8,000, and the network only has 15,000 units available.

There is no clever solver parameter that creates the missing 3,000 units.

If both commitments are modeled as hard constraints,

[ \sum_i x_{i,A,t} \ge 10{,}000, ]

[ \sum_i x_{i,B,t} \ge 8{,}000, ]

while supply requires

[ \sum_{i,j} x_{ijt} \le 15{,}000, ]

the correct mathematical conclusion is infeasibility. The useful work starts there.

Ask Which Constraints Are Actually Hard

Real organizations are full of constraints that are described as mandatory until violating one becomes inconvenient. That is dangerous modeling language.

A physical law is hard. You cannot ship inventory that does not exist. A regulatory restriction may be hard. You cannot legally ship a product into a market where it is prohibited.

A warehouse capacity may look hard but sometimes overtime, overflow storage, or an emergency transfer can expand it at a cost. A customer target may be contractual, internally negotiated, or merely a KPI somebody put on a dashboard three years ago.

Those are different things and should not automatically receive identical mathematical treatment.

For every major constraint, ask:

1. What happens operationally if we violate this?
2. Is violation physically impossible, legally prohibited, contractually penalized, or merely undesirable?
3. Who has authority to relax it?
4. How much can it be relaxed?
5. What does relaxation cost?
6. Is that cost linear, fixed, tiered, or dependent on duration?

If nobody can answer those questions, the model has exposed a problem in the operating process before it has exposed a problem in the mathematics.

Use Slack Variables Deliberately

One common way to represent a relaxable commitment is with a shortage or violation variable. Instead of requiring

[ \sum_i x_{i,A,t} \ge d_{A,t}, ]

write

[ \sum_i x_{i,A,t} + s_{A,t} \ge d_{A,t}, \qquad s_{A,t} \ge 0. ]

Then penalize (s_{A,t}) in the objective.

This makes the model mathematically feasible even when demand exceeds supply, but that alone does not make the model good. The penalty must mean something.

If you assign an arbitrary penalty of one million dollars because you “really do not want shortages,” the model may behave strangely elsewhere. It may pay absurd transportation costs, hold inventory in the wrong place, or distort another decision simply because the penalty coefficient dominates everything around it.

A better penalty comes from the economics of the violation where possible: lost contribution margin, contractual penalties, expected customer churn, expedite cost, downstream production stoppage, substitution cost, or another defensible consequence.

Not every consequence can be estimated precisely. That is fine. An uncertain economic estimate is usually more informative than an arbitrary giant number pretending to be certainty.

Feasibility Relaxation Is a Diagnostic Tool

When an existing model suddenly becomes infeasible, a feasibility relaxation can help identify the smallest or cheapest set of violations required to recover feasibility.

Conceptually, take selected constraints

[ a_k^Tx \le b_k ]

and introduce violation variables (v_k):

[ a_k^Tx \le b_k + v_k, \qquad v_k \ge 0. ]

Then solve something like

[ \min \sum_k w_k v_k. ]

The weights (w_k) matter enormously. If every violation has the same unit cost, the relaxation answers a mathematical question about total slack. It may not answer the business question you care about.

Violating one unit of warehouse capacity is not necessarily equivalent to violating one unit of a regulatory limit. In fact, the regulatory constraint may need to remain completely non-relaxable.

Think of feasibility relaxation as a controlled experiment: if the model is permitted to break selected rules, which rules does it break and by how much?

That answer can be extremely useful for debugging and operations. It should not automatically become the production decision.

IIS Is a Starting Point, Not a Root Cause

MILP solvers can often compute an irreducible infeasible subsystem, or IIS. An IIS is a subset of constraints and bounds that is itself infeasible, but becomes feasible if certain members are removed. It is one of the first tools I reach for when a formulation that should be feasible is not.

But an IIS is not a business explanation.

Suppose the IIS contains the inventory balance for SKU 421, a minimum customer allocation, a supplier outage restriction, and a lower bound on ending inventory. The solver has identified a conflicting mathematical subsystem. It has not told you whether the supplier outage data is wrong, the customer commitment is stale, the safety-stock rule should be soft, the starting inventory is incorrect, or the business genuinely has an impossible week ahead.

You still have to investigate the state and semantics behind those rows.

This is why constraint names matter. c_1847291 is useless at 2 A.M. A name like min_customer_allocation[customer=A,sku=421,week=2026-08-03] turns solver diagnostics into something an engineer or planner can actually trace.

Build Models That Explain Their Own Failure

Production optimization should be observable.

At minimum, log model status, objective value when available, best bound and gap, solve time, row and column counts, integer and binary variable counts, presolve reductions, major input totals, the number and magnitude of soft-constraint violations, and identifiers for the business entities involved in infeasibility diagnostics.

If infeasibility is possible in normal operations, build a diagnostic path before launch:

1. Solve the production model.
2. If infeasible, validate obvious input invariants.
3. Compute an IIS or targeted feasibility relaxation.
4. Translate affected constraints back to SKUs, vendors, locations, customers, and periods.
5. Produce an operational exception report.
6. Route the exception to whoever can actually change the conflicting commitment.

That is much better than returning “optimization failed” to an application and asking a data scientist to inspect a log file manually.

Separate Data Infeasibility From Business Infeasibility

This distinction saves enormous debugging time.

Data infeasibility means the model state is internally inconsistent because the inputs are wrong or incomplete. Examples include negative usable capacity caused by a bad join, duplicated demand, missing initial inventory, an outage date shifted by one week, incompatible units of measure, or a product assigned to no eligible facility.

Business infeasibility means the data may be perfectly correct, but the requested commitments cannot coexist. Examples include demand commitments exceeding supply, mandatory production exceeding labor capacity, minimum order quantities exceeding available budget, promised delivery dates earlier than physical lead times, or inventory targets competing for the same scarce units.

The first category usually requires fixing the pipeline. The second requires making a decision.

Do not hide the second category by automatically weakening every constraint until the solver returns an answer. Sometimes the most valuable output of the optimization system is a precise statement that management has promised more than the network can deliver.

Uncertainty Makes Feasibility More Subtle

A deterministic model can create false confidence around feasibility.

Suppose supplier capacity is represented as 20,000 units because that is the expected value. The plan may be perfectly feasible at 20,000 and impossible at 14,000.

The operational question is not only whether the plan is feasible under one assumed future. It is how fragile feasibility is across plausible futures.

You can examine this with scenarios. For scenario (\omega), let uncertain supply be (C_t(\omega)). Evaluate the policy across many plausible paths and track quantities such as

[ P(\text{commitment violation}), ]

expected shortage (E[S]), and tail shortage such as a high quantile or CVaR-style measure.

A plan that has zero shortage in the mean scenario but fails badly in 30% of plausible supply paths is not robust simply because the deterministic MILP returned OPTIMAL.

This is another reason to separate the decision policy from a single solved plan. You need to know what the system will do when reality moves away from today’s assumptions.

Do Not Confuse Feasible With Good

There is a temptation in optimization projects to celebrate once the model solves. That is a low bar.

A model can be feasible and economically terrible. It can also be infeasible and extremely informative.

After introducing relaxations, track total economic objective, violation cost, violation quantity by constraint family, number of entities affected, concentration of violations, frequency of violation across historical replays or scenarios, and stability of the resulting decisions.

If a soft constraint is violated every single run, stop calling it an exception. Either the target is structurally unrealistic or the penalty does not represent the business.

If a constraint is never active, ask whether it contributes anything to the model.

If a supposedly hard commitment repeatedly makes the model infeasible and leadership repeatedly overrides it, you have learned that the commitment is not actually hard. Model the real process.

A Practical Debugging Sequence

When a production MILP becomes infeasible, I generally work in this order.

First, reproduce the exact failing instance. Save the input snapshot, model version, configuration, and solver parameters. If you cannot reproduce the problem, everything after that becomes guesswork.

Second, run basic data checks outside the solver. Compare total supply with mandatory demand. Check capacities, bounds, units, dates, eligibility sets, and initial conditions. Many “optimization problems” are simple data contradictions.

Third, inspect presolve and the solver log. Sometimes the log immediately tells you that a variable bound or reduced subsystem is contradictory.

Fourth, compute an IIS if the model size and solver support make that practical. Map every returned row and bound to business language.

Fifth, run a targeted feasibility relaxation on constraints that are legitimately relaxable. Do not relax physical or legal restrictions merely because it is convenient.

Sixth, quantify the economic consequence of the required relaxation.

Finally, decide whether the fix belongs in data, formulation, policy, or operations.

Those are four different fixes. Teams waste months when they treat them as one.

What to Do in Practice

Before deploying an optimization model, create a constraint registry. For each important family, record its business meaning, owner, source data, whether it is hard or soft, permitted relaxation, and economic penalty if applicable.

Give every generated constraint a traceable name. Create automated sanity checks before model construction. Catch impossible totals and broken dimensions before paying the cost of building and solving a giant MILP. Make infeasibility diagnostics part of the product, not a notebook somebody runs after an incident.

And most importantly, preserve the signal.

If the business asks for 18,000 units from a network that can physically deliver 15,000, your job is not to make the red solver status disappear. Your job is to make the tradeoff explicit enough that somebody can decide which 3,000 units matter least.

That is what optimization is for.