Same Logic, Different Relaxation | Learn

The Integer Logic Can Be Right and the Model Can Still Be Bad

A common modeling mistake is to stop once the integer solutions look correct.

You write a formulation. You test a few cases. The binary variables behave the way you intended. The model returns a feasible answer. Done.

Not necessarily.

Two formulations can represent exactly the same valid integer solutions and still give the solver radically different information before integrality is enforced. One can produce a tight LP relaxation that points directly toward good integer solutions. The other can produce fractional nonsense that is technically legal in the relaxation but economically meaningless.

That difference matters because a MILP solver does not begin by magically understanding your business logic. It begins with relaxations, bounds, presolve, cuts, heuristics, and a search tree. If your formulation gives the solver weak bounds, you have made the search harder before tuning a single parameter.

This is one of the most practical ideas in MILP modeling:

The formulation is not only a description of feasible integer decisions. It is also information you give the solver about the space between those decisions.

A Supply Chain Example: Open a Lane Before You Ship

Suppose a distribution network can activate a transportation lane from a plant to a distribution center.

Let:

y = 1 if the lane is activated
y = 0 otherwise
x be the quantity shipped on the lane
U be the maximum possible shipment on the lane

The business logic is simple:

You cannot ship on a lane unless the lane is active.

A standard formulation is:

x ≤ U y
x ≥ 0

y ∈ {0,1}

For integer values of y, the logic is correct.

If y = 0, then x = 0.
If y = 1, then x may range from 0 to U.

Now suppose the true physical capacity of this particular lane is 500 units, but someone uses U = 1,000,000 because it is “definitely large enough.”

The integer logic is still correct.

The relaxation is not.

If the solver temporarily allows y to be fractional, a shipment of 500 units requires only:

y = 0.0005

If activating the lane costs $10,000, the LP relaxation pays only $5 of activation cost while receiving the full benefit of shipping 500 units.

That solution is impossible in the real business. But the relaxation is allowed to use it to compute a bound.

The result is a weak bound, a misleading picture of the economics, and potentially a much larger branch-and-bound tree.

The stronger formulation uses the tightest valid upper bound you can justify:

x ≤ 500 y

The integer feasible set has not changed. The solver’s view of the problem has.

Formulation Strength Is About the Fractional World

Practitioners often compare two formulations by asking:

Do they produce the same final answer?

That is necessary, but incomplete.

A better set of questions is:

Do they represent the same integer feasible set?
What solutions become legal when binary variables are relaxed to [0,1]?
How close is the LP bound to the best integer objective?
Does the relaxation preserve the economics of the real decision?
Does one formulation create extreme coefficient ranges or numerical problems?
Does one formulation expose structure that presolve and cuts can use?

The integer model describes what is allowed.

The relaxation describes what the solver is allowed to believe while proving it.

That second part is where many “equivalent” formulations stop being equivalent in practice.

Another Example: If One Period Starts, Later Periods Stay On

Suppose a temporary production line can be activated over a planning horizon. Once it starts, it must remain active for the rest of the horizon.

Let:

y_t = 1 if the line is active in period t

The clean formulation is:

y_t ≤ y_{t+1}    for all t

That is the logic directly.

A common modeling instinct is to introduce extra start variables, cumulative sums, or oversized linking constraints even when the business rule is only monotonic activation. Those formulations may still reproduce the same binary patterns, but they add variables and create more opportunities for fractional behavior.

Before adding machinery, ask:

What is the smallest mathematical statement that directly describes the business rule?

For this problem, the answer is the ordering relation itself.

A stronger formulation is not always a more complicated formulation. Often it is the opposite.

The Real Problem Framing Comes First

You cannot build a strong formulation if you have not identified the actual decision.

Before writing constraints, define the system in plain language.

What is the decision?

Is the business choosing:

how much to order?
whether to open a lane?
which supplier to use?
when to start production?
how to allocate scarce inventory?
which customers to prioritize?

Do not confuse a report field with a decision variable. A spreadsheet may contain 200 columns. That does not mean the model has 200 meaningful decisions.

When is the decision made?

A decision made today cannot use information that arrives next week.

This sounds obvious. It is violated constantly.

If the model chooses an order before demand is realized, then the order variable cannot quietly depend on realized demand. If a recourse decision happens after uncertainty is observed, model that timing explicitly.

What physically limits the decision?

The tightest useful bounds usually come from operations:

truck capacity
shelf space
supplier capacity
remaining demand
inventory position
production rate
warehouse throughput
contract limits
calendar time

These are not only business constraints. They are formulation information.

A loose upper bound often means the modeler has not finished understanding the operation.

Strong Bounds Are Usually Operational Facts

Suppose an order variable q_i is linked to a binary supplier-selection variable y_i:

q_i ≤ M y_i

The lazy question is:

What number is safely large?

The better question is:

What is the largest order that could ever be economically and physically useful for supplier i in this decision cycle?

Possible bounds include:

q_i ≤ supplier_capacity_i · y_i
q_i ≤ remaining_demand_i · y_i
q_i ≤ available_budget / unit_cost_i · y_i
q_i ≤ remaining_storage_capacity · y_i

Sometimes several bounds can be used together.

The strongest valid bound may be:

q_i ≤ min(
    supplier_capacity_i,
    remaining_demand_i,
    storage_limit_i,
    budget_limit_i
) y_i

This is not solver tuning. It is modeling.

And it is often more valuable than changing twenty solver parameters after the fact.

Uncertainty Changes What “Tight” Means

Supply chain bounds are rarely perfectly known.

Demand is uncertain. Lead times move. Capacity fails. Inventory records are wrong. A supplier that promises 10,000 units may deliver 7,000.

That does not mean every bound should become enormous.

Separate three things:

Physical limits that are truly hard.
Planning assumptions that are uncertain.
Risk buffers added because reality is noisy.

For example, warehouse cube may be a hard limit. Future demand is not. Supplier capacity may be scenario-dependent. Safety stock is a policy choice, not a law of physics.

If uncertainty affects a bound, model the uncertainty where it belongs instead of hiding it inside an absurdly large constant.

Possible approaches include:

scenario-specific capacity
chance constraints
robust bounds
recourse decisions
rolling re-optimization
explicit shortage or overflow penalties

The goal is not to make the deterministic model pretend uncertainty does not exist. The goal is to avoid using uncertainty as an excuse for mathematically meaningless bounds.

Measure the Relaxation, Do Not Argue About It

When comparing formulations, run experiments.

Track at least:

root LP objective
best integer objective
root gap
nodes explored
time to first feasible solution
time to a decision-acceptable gap
total runtime
cut counts
presolve reductions
numerical warnings
coefficient ranges

For a minimization problem, a simple root gap is:

(best_integer - root_bound) / abs(best_integer)

For a maximization problem, adjust the direction accordingly.

Suppose two formulations produce the same optimal integer solution of $1,000,000.

Formulation A has a root bound of $995,000.

Formulation B has a root bound of $300,000.

They may be logically equivalent at integer solutions. They are not giving the solver equivalent information.

Do not wait for a production timeout to discover this.

A Practical Formulation Comparison Workflow

When you have two ways to model the same logic, use a repeatable process.

1. Prove the integer logic

Check that both formulations allow exactly the intended integer decisions.

Use tiny test instances where you can enumerate feasible solutions if necessary.

2. Relax the integrality

Change binaries to continuous variables between zero and one.

Then inspect the solutions.

Ask:

What fractional behavior is now legal?

If the relaxation can buy 0.001 of a factory and receive full factory output, you have learned something important.

3. Compare root bounds

Solve the root relaxation or inspect the root-node log.

A materially better bound is evidence that one formulation is stronger.

4. Test representative instances

Do not benchmark one toy model.

Use instances that reflect:

normal days
peak volume
scarce capacity
loose capacity
high uncertainty
low uncertainty
large product counts
difficult network structures

5. Compare decision quality and computational behavior

A formulation that solves quickly but represents the wrong operation is useless.

A formulation that is mathematically beautiful but misses the decision deadline may also be useless.

The real target is a correct model that produces good decisions within the operational time budget.

Implementation Notes That Matter

Keep bounds at the correct level of detail

A single global M is usually weaker than item-, lane-, location-, or period-specific bounds.

Prefer:

x_{i,j,t} ≤ U_{i,j,t} y_{i,j,t}

over:

x_{i,j,t} ≤ 10^9 y_{i,j,t}

if valid granular bounds are available.

Generate bounds from trusted data

A tight bound based on bad data can cut off valid decisions.

Treat bound-generation logic as production code:

validate units
handle missing values
log unusual values
version assumptions
test edge cases

Watch coefficient ranges

A model mixing coefficients like 0.000001 and 1,000,000,000 deserves attention.

Even if the logic is valid, poor scaling can create numerical trouble and make tolerances harder to interpret.

Save comparable solver artifacts

For important models, store:

model version
data snapshot
solver version
parameter file
log file
objective components
runtime metrics

Otherwise, “the old formulation was faster” becomes folklore instead of evidence.

Common Failure Modes

1. Declaring formulations equivalent because the final answer matched once

One instance proves almost nothing about computational behavior.

2. Using giant Big-M values for convenience

“Definitely large enough” is not a modeling principle.

3. Adding variables because the algebra looks familiar

Every auxiliary variable should earn its place.

4. Tuning the solver before fixing the formulation

Parameters cannot fully compensate for weak mathematical information.

5. Tightening a bound until the model becomes wrong

A strong invalid formulation is still invalid.

6. Ignoring uncertainty when deriving bounds

A bound based on a point forecast may accidentally forbid plausible high-demand decisions.

7. Optimizing benchmark runtime instead of operational value

A 30-second model with bad decisions is worse than a 3-minute model that materially improves the business, assuming the decision window allows three minutes.

What to Do in Practice

When a MILP is slow, do not begin with a random parameter sweep.

First ask:

What is the actual business decision?
What integer logic must be represented?
What does the LP relaxation allow that reality does not?
Which bounds can be tightened using real operational facts?
Are there unnecessary variables or indirect constraints?
Is uncertainty modeled explicitly or hidden inside giant constants?
What does the root-node log say?
Does the stronger formulation improve the metric that matters: useful decisions delivered on time?

The best modelers do not only encode the rules correctly.

They think about what the solver sees before the binaries become binary.

That is where formulation strength lives.

And in real MILP systems, that invisible fractional world can determine whether the model solves in seconds, hours, or not at all.