Do Not Build Constraints You Do Not Need | Learn

A surprisingly common optimization problem is not that the solver is slow.

The problem is that we handed the solver a mountain of mathematics it never needed.

Suppose a supply chain model has 50,000 products, 100 locations, 52 weeks, and a family of business rules that can potentially apply across many combinations. It is easy to write a loop that generates every legal constraint before the solve starts. The model is mathematically correct. It is also possible that 99.9% of those rows will never matter to the decision.

That distinction matters.

A constraint can be valid without being useful in the initial model.

Constraint generation exploits that fact. Instead of building every possible constraint up front, solve a smaller problem, inspect the proposed solution for violations, add the constraints needed to eliminate those violations, and solve again.

This is not a trick for making a bad formulation look clever. It is a modeling strategy for problems where the full mathematical description is large but only a small part of it is active around the decisions we actually make.

Start with the decision

Before reaching for constraint generation, write down what the model is deciding.

For a simplified supply planning problem, we might have:

x[i,t]: quantity ordered for item i in period t
y[i,t]: binary variable indicating whether an order is placed
I[i,t]: ending inventory
u[i,t]: unmet demand or lost sales

The objective might minimize purchase, holding, shortage, setup, and transportation costs:

[ \min \sum_{i,t} c_i x_{i,t}

h_i I_{i,t}
p_i u_{i,t}
f_i y_{i,t}. ]

Inventory balance, order activation, supplier capacity, and basic bounds belong in the initial model because they define the core feasible decision.

Now imagine an additional rule: for every vendor, every rolling 8-week interval may consume no more than a contractual volume allowance.

For vendor v and window starting at s:

[ \sum_{i \in v}\sum_{t=s}^{s+7} x_{i,t} \le C_{v,s}. ]

With enough vendors, items, horizons, modes, regions, and overlapping windows, this family can become enormous.

But the optimal solution may come close to violating only a handful of those windows.

That is where constraint generation becomes interesting.

The basic loop

The algorithm is almost embarrassingly simple.

Build a relaxed model without the expensive constraint family.
Solve it.
Inspect the solution.
Find constraints that the solution violates.
Add those constraints.
Re-solve.
Repeat until no violations remain.

Conceptually:

build core model

repeat:
    solve model
    violations = find_violations(solution)

    if violations is empty:
        stop

    add violated constraints

If the separation step is exact and the loop terminates with no violations, the final solution satisfies the full constraint family even though most of that family was never instantiated.

The important work is therefore not the loop. It is the separation problem: given a candidate solution, can you efficiently determine whether any omitted constraint is violated?

A practical supply chain example

Consider transportation capacity across rolling windows.

A naive implementation might generate every capacity constraint for every lane and every possible interval length:

[ \sum_{t=a}^{b} q_{l,t} \le C_{l,a,b} \quad \forall l,a,b. ]

If there are 104 periods, each lane has thousands of possible intervals. Multiply that by thousands of lanes and model construction alone can become painful.

Instead, solve with the ordinary weekly constraints first. Then calculate cumulative shipped volume for each lane:

[ Q_{l,t} = \sum_{\tau=1}^{t} q_{l,\tau}. ]

Any interval volume is then:

[ Q_{l,b} - Q_{l,a-1}. ]

The separation routine can scan for intervals whose volume exceeds the applicable limit. Only those violated interval constraints are added.

The solver does not need to reason about every theoretical interval if the proposed plan never puts most of them at risk.

Ask whether the constraint family is actually separable

Constraint generation works best when checking a candidate solution is substantially cheaper than representing every possible restriction inside the MILP.

Good questions to ask are:

Can I detect violations directly from the incumbent values?
Can the check be vectorized or computed with cumulative sums?
Is there a polynomial-time separation algorithm?
Does the business rule naturally apply to subsets, paths, windows, groups, or combinations that can be searched after solving?
Are only a small fraction of possible constraints likely to bind?
Is model construction or memory a meaningful part of runtime?

If finding the most violated constraint requires solving another problem nearly as difficult as the original MILP, constraint generation may still be useful, but the economics change.

You are moving complexity from model size into separation.

That can be a good trade. It is not a free trade.

Do not confuse this with deleting random constraints

The relaxed problem is allowed to propose solutions that violate omitted constraints. That is the point.

What makes the method valid is that we check those solutions and keep adding restrictions until the final candidate satisfies the full model.

If you simply remove constraints because they usually do not bind and never check them again, you have changed the optimization problem.

Sometimes that approximation is acceptable. But call it what it is.

Constraint generation is different because the omitted constraints remain logically part of the model even when they are not initially present in the solver instance.

Add the right violations

Suppose one iteration discovers 20,000 violated constraints.

Should you add all 20,000?

Maybe. Maybe not.

Adding every violation usually reduces the number of outer iterations, but it can quickly recreate the giant model you were trying to avoid. Adding only the single most violated row keeps the model tiny but may require hundreds of solves.

A practical compromise is to add a batch of meaningful violations.

For example:

add the top 100 violations by absolute magnitude;
add every violation above a material tolerance;
add the worst violation per vendor or resource;
add violations that are structurally different rather than thousands of nearly identical rows.

Benchmark this. There is no universal best batch size.

The metric is total wall-clock time to a valid decision, not how elegant the loop looks.

Tolerances matter

Suppose a capacity is 10,000 units and the candidate solution uses 10,000.000001.

You probably do not want to add a new row, rebuild the model, and solve again because of floating-point noise.

Define a violation tolerance that makes sense for both the solver and the business quantity:

[ \text{violation} = \text{lhs}(x) - \text{rhs}. ]

Add a constraint when:

[ \text{violation} > \epsilon. ]

The value of epsilon should respect scale. A tolerance appropriate for binary counts is different from one appropriate for millions of dollars or kilograms.

This is another reason numerical scaling matters. Poorly scaled models make it harder to distinguish a real operational violation from numerical residue.

Practitioners often use these terms loosely, which creates confusion.

A constraint in the original formulation defines the actual feasible set. If it is omitted initially and later generated when violated, we are doing constraint generation.

A valid inequality or cutting plane may not be required to define feasibility at all. It can be added because it removes fractional LP solutions and strengthens the relaxation.

A lazy constraint is commonly enforced through solver callback machinery while the branch-and-bound search is running rather than through an explicit outer solve-check-add loop.

The implementation mechanics differ, and solver APIs place specific restrictions on what can be added in different callbacks.

Do not start with the API feature. Start with the mathematics.

Ask first: is this row necessary for feasibility, or is it only intended to improve the relaxation?

Then choose the appropriate implementation.

Why this can help more than solver tuning

Suppose your model has 12 million rows and takes 90 seconds just to construct, transfer, presolve, and allocate memory before meaningful search begins.

Changing a branching parameter is unlikely to fix the real problem.

If 11.5 million of those rows belong to a constraint family that almost never matters, reducing the initial formulation to 500,000 rows can attack the bottleneck directly.

Measure at least:

data preparation time;
model construction time;
number of variables;
number of constraints by family;
nonzero count;
presolve time;
root relaxation time;
time to first feasible solution;
time to target gap;
peak memory;
number of generation rounds;
constraints added per round;
separation time.

A single solve_time metric hides too much.

I have seen teams spend days tuning a solver when the expensive part was Python building millions of objects the solver immediately removed in presolve.

That is not a solver problem.

Presolve is giving you information

If the solver consistently removes 95% of one constraint family during presolve, do not immediately celebrate the presolver.

Ask why you generated those rows in the first place.

Presolve statistics can expose modeling opportunities. They tell you which structure is redundant, fixed, dominated, or irrelevant on the instances you are solving.

That does not mean every presolved row should be removed from your code. Presolve can exploit interactions that are difficult to reproduce safely.

But a huge and repeatable reduction is worth investigating.

The log is not just a performance report. It is evidence about the formulation.

Uncertainty changes which constraints matter

A constraint that never binds under the mean forecast may bind constantly under realistic demand or lead-time scenarios.

This is where deterministic benchmarking can mislead you.

Imagine a warehouse capacity constraint. Under expected demand, inventory remains comfortably below the physical limit. Under low-demand scenarios, inventory accumulates and capacity becomes critical.

If your constraint-generation logic is tested only against the deterministic base case, you may conclude the family is irrelevant.

It is not irrelevant. Your test set is weak.

Benchmark across representative states and uncertainty realizations:

high and low demand;
delayed receipts;
supplier outages;
promotion spikes;
excess starting inventory;
constrained transportation;
unusual MOQ interactions.

The question is not whether a constraint binds on average.

The question is whether the policy can encounter states where it matters.

Be careful with scenario models

Stochastic programs can create an especially ugly explosion because constraints may be replicated across scenarios.

Suppose 2,000 scenarios each contain 50,000 potential service, capacity, or recourse restrictions. The mathematical model can become huge before branch-and-bound even begins.

Before generating all of them, ask whether some restrictions can be separated after candidate decisions are known.

Also ask whether the model needs every scenario in the optimization at all. Scenario count, scenario quality, and constraint generation are different design decisions, but they interact strongly through memory and runtime.

Do not optimize one component in isolation.

The production objective is to generate a good decision within the available latency and compute budget.

The separation routine needs tests too

One dangerous failure mode is a fast optimization model paired with a buggy violation checker.

Then the algorithm terminates and proudly reports a solution that is infeasible under the business rules.

Treat separation code as first-class optimization code.

For small instances, generate the full formulation and compare it against the constraint-generation version. They should produce equivalent feasible sets and, within tolerances, the same optimal objective.

Create adversarial unit tests where you know a specific omitted constraint must be violated.

Log:

the constraint family;
entity identifiers;
left-hand side;
right-hand side;
violation magnitude;
iteration discovered;
iteration added.

If a planner says, “This schedule violates our 8-week vendor agreement,” you should be able to trace whether the separation routine checked that exact rule.

Constraint generation can expose bad business rules

There is a useful side effect here.

Once you log which constraints are actually generated, you get empirical evidence about which rules affect decisions.

Suppose the business maintains 40 complicated policy families, but six months of production runs show that 31 are never generated and never close to violation.

That does not automatically mean they should be deleted. Some may protect against rare but catastrophic states.

But now you can ask better questions:

What event is this rule protecting us from?
Has that event occurred historically?
Is the rule physical, contractual, or merely inherited?
Could the consequence be represented economically instead?
Should this be a hard constraint at all?

Optimization is useful here because it forces vague operational language into testable logic.

Failure modes

Constraint generation is powerful, but there are predictable ways to misuse it.

The omitted constraints are almost always active

If every iteration adds another huge batch and the final model contains nearly every possible row, you have added orchestration overhead without reducing the problem much.

Build the important family up front.

Separation is slower than solving

A 10-second MILP followed by a 15-minute Python loop checking every combination is not an improvement.

Profile the separation routine like any other algorithm.

The relaxation is too weak

Removing constraints can make the initial MILP dramatically easier to build but much harder to solve because the relaxation permits absurd solutions.

In that case, seed the model with a useful subset of constraints or add strengthening inequalities while still generating the expensive family dynamically.

You add duplicates

Repeatedly adding the same row wastes memory and can make debugging miserable.

Give generated constraints stable keys and maintain a set of what has already been added.

The business rule cannot be checked exactly

If your violation detector is heuristic, then “no violations found” does not prove feasibility.

Be explicit about that distinction.

You optimize a toy instance

A strategy that works beautifully on one vendor and 20 SKUs may collapse when applied to 10,000 vendors with shared resources and scenario replication.

Benchmark distributions of production-sized instances, not one demo.

A production architecture

A robust implementation can be separated into five components.

1. Core model builder

Build variables, objective terms, state transitions, and constraints that are always required.

2. Solver wrapper

Solve with explicit limits and capture incumbent quality, bound, gap, runtime, node count, and status.

3. Separation engine

Given a candidate solution, return structured violation records. Keep this logic independent enough that it can be tested without running the full optimizer.

4. Constraint registry

Track which generated rows have already been added and why.

5. Decision validator

After termination, independently verify the final plan against all business-critical rules before publishing it downstream.

That last step is worth having even when you trust the algorithm. Production systems fail in more creative ways than mathematical proofs anticipate: stale data, unit conversions, missing entities, configuration drift, and code paths that did not exist in the notebook.

Measure decision quality, not just model size

A smaller model is not automatically a better system.

Track technical metrics such as runtime and memory, but also evaluate the resulting policy on business outcomes:

expected profit or cost;
shortage cost;
excess inventory;
service outcomes;
expedite usage;
capacity violations;
decision stability;
infeasible production recommendations;
regret versus a stronger offline benchmark.

If constraint generation saves 80% of runtime but a bad stopping rule occasionally publishes infeasible orders, it is a failure.

The point is not to win a model-size contest.

The point is to make good executable decisions reliably.

What I would do in practice

If I inherited a large MILP with painful build time or memory usage, I would not immediately rewrite it around callbacks.

I would first instrument the current system.

Count rows and nonzeros by constraint family. Read the presolve log. Identify which families dominate construction time and memory. Measure how often those constraints bind across a representative set of historical and stressed instances.

Then choose one large, sparse-active family with a cheap exact violation check.

Implement an outer solve-check-add loop first. It is easier to reason about, easier to test, and easier to compare against the full formulation.

Run both approaches on small instances where the full model is tractable. Verify objective equivalence and final feasibility. Then benchmark larger instances and experiment with violation batch sizes, seeded constraints, and tolerances.

Only after the mathematics and separation logic are proven would I consider moving generation into solver callbacks for tighter integration.

That sequence matters.

Optimization engineering has a tendency to jump from “the model is slow” directly to exotic solver features. Often the better move is much simpler: understand what the solver is being asked to carry.

A business may have millions of theoretically valid restrictions.

Your current decision may care about fifty of them.

Do not make the solver drag the other 999,950 through the entire search unless you have a reason.