MILP modelling
Depots, routes and shifts are yes-or-no decisions, and a spreadsheet weighs them one at a time. A well-built MILP model weighs them all together.
- Free 30-minute call
- No commitment
- You own the code
In short: A mixed-integer linear program (MILP) is a model for planning problems with yes-or-no decisions, such as opening a depot. Goal and rules are linear: everything grows in proportion, so two trucks cost twice as much as one. The result is the best plan that keeps every rule.
The problem
You decide which depots open, which routes run and who works which shift. Each choice is yes or no, and each one changes what the others cost. A spreadsheet checks them one at a time and never sees the whole. Maybe you tried a model already, and it never finished in time.
What changes
Today, you test depot and shift options one by one and hope the combination works. Our model weighs every choice together and returns the cheapest plan that keeps your rules. You check that plan instead of building it.
How it works
Mixed-integer linear programming (MILP) suits exactly these decisions. The model has a goal, such as the lowest cost. It also has rules, called constraints. Both are linear: everything grows in proportion, so two trucks cost twice as much as one. Mixed-integer means some decisions can’t be split. A depot is open or closed, never half open.
The hard part is the formulation, how your problem is written down as maths. Most failed models went wrong there, long before anyone touched a solver setting. Often two plans are the same, only with the names swapped, like truck 1 and truck 2. We add rules so the search checks such plans only once. This is called breaking symmetry. Where a cost doesn’t grow in proportion, we rewrite it in a linear form. And we take care with every on-off rule.
How big should big-M be?
Big-M is the classic way to switch a rule on or off. Say a depot ships nothing unless it’s open: shipments ≤ M × open. M must be at least the most that depot could ever ship. Too small, and you cut off plans that would work. Too large, and the solver’s preview of the problem, which allows half-open depots, drifts far from reality. Then the search takes much longer.
There’s a nastier effect too. Gurobi’s numerical guide calls big-M constraints “a regular source of instability”. Its default tolerance treats a binary value of 0.0000099999 as zero. With M at one million, a closed depot can then ship almost ten units for free. Gurobi also recommends that the largest number in the model be at most a million times the smallest.
So we set M to the smallest value your data allows, depot by depot. Where no small value exists, we use indicator constraints, which hand the on-off logic to the solver directly. They’re numerically safer and sometimes slower, so we compare both. A solver’s run time depends partly on chance. So we run each variant several times, each with a different random starting value. One run of each proves very little.
We build and tune these models for Gurobi, CPLEX, HiGHS or SCIP, whichever fits your problem. The honest boundary: non-linear goals, very large problems or real-time answers can call for a different technique. When they do, we tell you and use the right one.
When it isn’t the answer
The honest boundary: non-linear goals, very large problems or real-time answers can call for a different technique. When they do, we tell you and use the right one.
Common questions.
Something else? Ask us directly.
Look at two numbers. First, let the solver answer the yes-or-no decisions with fractions, such as a half-open depot. This simpler version is called the LP relaxation. See how close its result lands to the best workable plan. The closer, the less searching is left. Second, run times on a fair test: the same realistic cases, chosen in advance, on the same machine. A model that wins on one case only has proved very little.
Sometimes, and you only find out by testing. Valid inequalities are extra rules that cut off fractional answers without losing any workable plan. Practitioners on Operations Research Stack Exchange report that they help most when the model’s LP relaxation is weak. That is the simpler version of the model that allows fractions. Weak means its result lands far from the best workable plan. Results also shift with each solver version, so we retest after upgrades.
Try both, with short time limits. Symmetry means many plans that differ only in labels, like two identical trucks swapping routes. Modern solvers detect some of it on their own, and they have settings for how hard to try. Hand-written rules still win on some models. On others they get in the way.
Your own data decides. HiGHS solves linear and mixed-integer models and comes under the MIT licence, so it costs nothing to ship. We run your model on both and compare times on your own cases. If HiGHS finishes inside your planning window, the licence money stays with you.
Sometimes they can, and then we’ll say so. Standard tools are built for an average problem, though. With MILP modelling, we start from yours: its size, its rules and the exceptions nobody wrote down. That is why the plan fits your operation better.
You don’t need either to start. We build the model from the data you’ve got, messy or not, and cleaning it up is part of the job. You get a documented system your team can maintain, and we train them until they can run it long after we’ve left.
It starts with a free 30-minute call about your operation and the model that would fit it. Then we build a working prototype and run it on your numbers. You’ll see results before you commit to anything bigger.
Similar pages.
Terms on this page
Every abbreviation explained in plain words, in our article “Metrics and methods”.
- LPLinear programming
- MILPMixed-integer linear programming
- LP relaxation
- Gurobi
- CPLEXIBM CPLEX
- HiGHSHiGHS
- SCIPSCIP
Tell us what you’re planning.
In a free 30-minute call with a specialist, you find out whether optimisation can help.
- Free, no commitment
- You talk to a specialist directly
- A clear go or no-go