Fix the Formulation Before You Tune the Solver | Learn

A MILP can be mathematically correct and still be a terrible model for a solver.

That distinction matters. Two formulations can describe exactly the same feasible integer decisions and produce exactly the same optimal answer, yet one solves in seconds while the other burns through a time limit without proving much of anything. When that happens, changing solver parameters is usually not the first thing I want to do. I want to know what mathematical problem I actually handed the solver.

This is one of the most practical lessons in optimization: equivalent integer models are not necessarily equivalent computational models.

If you are deciding whether formulation A is better than formulation B, there are useful things you can inspect before running a full benchmark. But eventually you should test them. Solver performance is an empirical property of the formulation, the data, the instance distribution, and the solver implementation together.

The right workflow is therefore not “prove which formulation is faster” and it is not “run both once and pick the winner.” It is structural analysis first, controlled experiments second.

Start with the decision

Suppose you are building a supply planning model. For item $i$ and period $t$, you decide an order quantity $x_{it}$ and whether an order is activated using binary variable $y_{it}$.

A common linking constraint is

$$ x_{it} \le M y_{it}. $$

If $M=10{,}000{,}000$ because somebody wanted a number that was “definitely big enough,” the integer logic may be correct. But the LP relaxation can let $y_{it}=0.00001$ while still permitting a meaningful order quantity. The relaxation is now describing behavior that makes no operational sense.

If the largest possible order is actually 4,000 units, then

$$ x_{it} \le 4000 y_{it} $$

represents the same integer decision much more tightly.

Better yet, perhaps inventory capacity, remaining demand, supplier capacity, and the buying horizon imply a period-specific upper bound $U_{it}$:

$$ x_{it} \le U_{it} y_{it}. $$

That is not cosmetic cleanup. You have changed the geometry of the continuous relaxation the solver uses to reason about the integer problem.

Before comparing formulations, be explicit about what the model is deciding:

What are the actual operational actions?
Which decisions are discrete and why?
Which variables are states, such as inventory or backlog?
Which variables merely exist to express logic?
What information is known when each decision is made?
Which constraints are physical limits and which are policy rules?

A formulation should be judged partly by how faithfully and economically it represents that decision structure.

The LP relaxation is your first diagnostic

For a minimization MILP, removing integrality gives an LP relaxation whose objective is a lower bound on the integer optimum. A tighter lower bound generally gives the solver a better starting point for branch-and-bound.

Suppose the optimal integer objective is 100. Formulation A has a root LP objective of 98 while formulation B has a root LP objective of 40. All else equal, A is giving the solver substantially more information about where the true optimum lives.

This is why formulation strength matters.

A useful root-gap calculation is

$$ \text{root gap} = \frac{|z_{IP}-z_{LP}|}{\max(1,|z_{IP}|)}. $$

For benchmark instances where you know or can obtain a good integer solution, compare that gap across formulations. If you do not know the optimum, you can still compare root bounds, incumbent quality, and bound progression under controlled conditions.

But do not turn “stronger relaxation” into a religion. A stronger formulation can require many more rows, columns, nonzeros, or auxiliary variables. Solving the root LP itself may become expensive. The formulation with the best theoretical relaxation is not automatically the formulation with the shortest wall-clock time.

That tradeoff is exactly why testing still matters.

Look for strength you can explain

The best formulation improvements usually have a structural explanation.

Tighten bounds

Bounds are free information. If a variable can never exceed 500, do not give it an upper bound of one billion.

In supply chain models, useful bounds often come from:

remaining horizon demand,
warehouse capacity,
supplier capacity,
budget,
truck capacity,
shelf life,
maximum inventory position,
MOQ or pack structure,
known open purchase orders.

Derive bounds from the business whenever possible rather than inventing constants.

Disaggregate weak aggregate logic

Suppose several quantities $x_j$ require a common activation $y$. An aggregate constraint such as

$$ \sum_j x_j \le M y $$

may be valid, but individual bounds

$$ x_j \le U_j y \quad \forall j $$

can communicate much more structure. Depending on the problem, keeping both may strengthen the model further.

The point is not that disaggregation is always better. The point is that the relaxation should reflect the actual logical implications of the integer decision as closely as practical.

Remove unnecessary symmetry

If ten mathematically interchangeable variables can represent the same operational decision, the solver may spend time exploring equivalent solutions.

Symmetry often appears when you create artificial slots, identical resources, interchangeable bins, or duplicated logical constructs. Ask whether those labels matter to the business. If they do not, consider a formulation that does not force the solver to rediscover that equivalence through search.

Use the right variable for the logic

Sometimes a tortured collection of big-M constraints exists because the model is representing the wrong thing.

If the business decision is “open this vendor order,” model that activation explicitly. If the decision is “choose exactly one transportation mode,” represent the mode choice directly. If inventory is a state, use inventory balance rather than reconstructing it repeatedly from cumulative expressions unless there is a good computational reason not to.

Good formulation starts with good problem framing.

Constraint count is not model quality

A smaller model is not necessarily a faster model.

People routinely compare two formulations and say, “This one has 30% fewer constraints, so it should be better.” Maybe. Maybe not.

A model with 100,000 informative constraints can solve faster than a model with 20,000 weak ones. Conversely, adding every valid inequality you can think of can make LP solves so expensive that the stronger relaxation loses in practice.

Track at least:

rows,
columns,
binary and general integer variables,
nonzeros,
coefficient ranges,
presolved model size,
root relaxation time,
root bound,
incumbent quality,
branch-and-bound nodes,
final optimality gap,
total wall-clock time.

These tell a story together. None is the scoreboard by itself.

Numerics are part of formulation quality

Imagine one constraint contains coefficients around $10^{-6}$ and another contains coefficients around $10^9$. The mathematics may be valid, but you are asking floating-point algorithms to operate across a huge numerical range.

This can create unstable relaxations, tolerance surprises, weak effective constraints, and difficult linear systems.

Look at the solver log. Check coefficient statistics. Ask whether the units make sense.

If one variable is measured in individual units and another in hundreds of millions of dollars, rescaling may make the model easier to reason about numerically. If a penalty coefficient is twelve orders of magnitude larger than ordinary costs because you wanted to make a soft rule “basically hard,” you should probably revisit the model semantics too.

A giant penalty is often a hidden constraint with worse numerics.

Uncertainty changes what a good formulation means

Supply chain models rarely operate on one deterministic future. Demand changes. Lead times move. Capacity disappears. Costs change. Forecasts are revised.

That means formulation quality should not be evaluated on one hand-picked instance.

Suppose formulation A wins spectacularly on a low-demand week because presolve eliminates most of the model, while formulation B is consistently faster when capacity is tight and many binary decisions become active. If production mostly lives in the second regime, the first benchmark is misleading.

Build an instance set that reflects the operating distribution:

normal demand,
peak demand,
low inventory,
high inventory,
tight capacity,
loose capacity,
large vendors,
small vendors,
many active MOQs,
few active MOQs,
different forecast vintages.

You are not optimizing a formulation for a toy instance. You are selecting a computational policy for a stream of future problems.

Benchmark like an experiment

Once the structural review is done, test.

Keep the comparison controlled. Use the same solver version, hardware, thread policy, time limit, stopping criteria, and instance set. Avoid aggressively tuning one formulation while leaving the other at defaults unless parameter interaction is itself what you are studying.

For each formulation-instance pair, record metrics such as:

Metric	Why it matters
Model build time	Formulation overhead can matter in production
Presolve time	Shows how much structure is eliminated
Root LP time	Strong models can still have expensive roots
Root bound/gap	Measures relaxation usefulness
Time to first feasible solution	Important when decisions have deadlines
Incumbent at 10s/30s/60s	Measures anytime behavior
Best bound at 10s/30s/60s	Measures proof progress
Nodes explored	Useful diagnostic, not a standalone objective
Final gap	Critical when runs hit the time limit
Total runtime	Relevant when optimality is actually required

Do not summarize everything with mean runtime. MILP runtime distributions can be ugly. Report medians, percentiles, timeout rates, and performance by instance class.

If a production service has a 120-second deadline, the most important metric may be the percentage of instances that produce an acceptable decision within 120 seconds—not the average time to mathematical optimality.

Compare decisions, not just proofs

Optimization systems exist to make decisions.

Suppose formulation A proves optimality in 90 seconds. Formulation B reaches a 0.4% gap in 20 seconds and then spends the remaining time proving the bound. If the production decision from B at 20 seconds is economically indistinguishable from the proven optimum, that matters.

For operational models, evaluate:

objective value of the incumbent,
realized profit or cost under simulation,
service outcomes,
inventory exposure,
capacity violations or relaxations,
decision stability,
runtime reliability.

The solver’s optimality gap is a mathematical diagnostic. It is not automatically the business loss from stopping early.

A 2% MIP gap does not mean the decision is 2% worse than the best operational policy. Conversely, a tiny MIP gap does not mean your model represents uncertainty, economics, or recourse correctly.

Keep computational optimality and decision quality separate.

Solver tuning comes after the model has earned it

Modern MILP solvers expose a lot of parameters. That makes it tempting to treat performance problems as tuning problems.

Sometimes tuning helps. But if the formulation contains loose big-M values, unnecessary binaries, poor bounds, numerical garbage, or duplicated symmetry, parameter tuning is working downstream of the actual problem.

A practical order of operations is:

Verify the decision model and data.
Inspect bounds and coefficient ranges.
Inspect presolve and the root relaxation.
Look for weak logical formulations and symmetry.
Compare alternative formulations on representative instances.
Only then test solver parameter changes that have a reason behind them.

Do not randomly sweep dozens of solver parameters and call the best historical combination an optimization breakthrough. You can overfit solver settings too.

Failure modes I see repeatedly

Testing on one instance

MILPs are instance-dependent. A formulation that wins one benchmark can lose badly elsewhere. Use a representative suite.

Using only runtime

If both runs time out, “120 seconds versus 120 seconds” tells you nothing. Compare incumbent quality and bounds over time.

Assuming fewer binaries always wins

Binary count matters, but structure matters more. Replacing useful binaries with weak continuous logic can make things worse.

Adding giant M values for safety

A huge $M$ does not make the formulation safer. It often makes the relaxation weaker and the numerics worse. Derive the smallest valid bound you can defend.

Confusing model build time with solve time

A sophisticated formulation may solve faster but take longer to construct. In a real service, both count against latency.

Tuning before reading the log

If you have not looked at presolve, coefficient ranges, root behavior, incumbent progression, and bound progression, you are tuning without a diagnosis.

Optimizing the benchmark instead of the system

A formulation that is amazing on last month’s instances can still fail when the operating regime shifts. Keep benchmark sets broad and refresh them.

What I would do in practice

If I inherited a slow MILP tomorrow, I would not begin with a parameter file.

I would first write down the actual decision and the operational meaning of every major variable family. Then I would inspect the formulation for loose bounds, unnecessary binaries, oversized big-M constants, artificial symmetry, duplicated logic, and badly scaled coefficients.

Next I would run the LP relaxation and read the solver log. I would compare the root bound to known good integer solutions where available. I would look at presolve reductions and ask what remains hard after presolve.

If I had an alternative formulation, I would benchmark both on a fixed suite of representative historical and stress-test instances. I would collect the full solve trajectory, not just the final runtime.

Then I would evaluate the resulting decisions under the actual operational metric—ideally using replay or simulation when uncertainty matters.

Only after that would I spend serious time tuning the solver.

The broader lesson is simple: the formulation is part of the algorithm.

You do not hand a solver a business problem. You hand it a mathematical representation of a business problem. The quality of that representation determines what the solver can infer before it starts enumerating possibilities.

A good solver can do impressive things with a strong model. It cannot rescue every weak formulation with parameter magic.