NEW: The Decision Factory — a novel about decisions under uncertainty. Get it on Amazon
Optimization · · Adam DeJans Jr.

When to Use Mixed-Integer Programming

MILP is powerful — but it's not always the right tool. Here's a practical guide to when integer programming shines and when you should reach for something else.

optimizationmilpheuristicsdecision-making

Not Every Problem Deserves a Solver

There’s a pattern in optimization teams that goes something like this: someone learns mixed-integer programming, gets excited, and starts trying to formulate everything as an MIP. Scheduling? MIP. Routing? MIP. Deciding where to eat lunch? Probably MIP.

The instinct isn’t wrong — MILP is one of the most powerful tools in the optimization toolbox. Modern solvers like Gurobi, CPLEX, and HiGHS can handle problems with millions of variables and constraints. But power doesn’t mean universality. The right question isn’t “can I model this as a MIP?” — it’s “should I?”

Where MILP Dominates

MILP is the right tool when your problem has these characteristics:

Discrete decisions. If you’re choosing between options — which facilities to open, which orders to assign to which trucks, which production lines to schedule — you’re in MIP territory. Binary and integer variables are the language of discrete choice, and solvers are built to handle them.

Hard constraints that must be respected. Capacity limits, regulatory requirements, contractual obligations, physical laws — MILP excels at finding the best solution that satisfies all constraints simultaneously. Unlike heuristics, a feasible MIP solution is provably feasible.

A clear objective to optimize. Minimize cost. Maximize profit. Minimize makespan. If you can write down what “good” means as a linear (or quadratic) function, MILP gives you a principled way to find the best answer, not just a good one.

Moderate problem size with complex structure. Problems with a few thousand to a few hundred thousand integer variables, especially those with tight LP relaxations and good structure, are the sweet spot. This covers a huge range of real-world applications: production planning, network design, crew scheduling, portfolio optimization, and more.

Where MILP Struggles

Knowing when not to use MILP is just as important:

Massive combinatorial problems with weak relaxations. Some problems — like the traveling salesman problem at scale, or bin packing with thousands of items — have LP relaxations so loose that the solver spends forever in the branch-and-bound tree. You might get a feasible solution quickly, but proving optimality (or even getting within 1% of optimal) can take hours or days.

Real-time decisions under millisecond latency. If you need an answer in 10 milliseconds — think real-time bidding, high-frequency trading, or per-request routing — MILP is too slow. Even a well-formulated model needs time to load, presolve, and solve. For these applications, precomputed lookup tables, trained ML models, or hand-tuned heuristics are better choices.

Problems dominated by uncertainty. A deterministic MIP assumes you know the data. If the dominant challenge is that demand is stochastic, travel times are random, or prices fluctuate wildly, you might need stochastic programming, robust optimization, or simulation-based approaches. You can still use MIP as a component of these methods, but a single deterministic model will give you a plan that’s optimal for a world that doesn’t exist.

Problems where “good enough” is fine. If a solution that’s 5-10% worse than optimal is perfectly acceptable — and the alternative is spending two weeks formulating a MIP — a well-designed heuristic might be the pragmatic choice. Greedy algorithms, local search, and metaheuristics can produce excellent solutions in a fraction of the development time.

The Decision Framework

When you encounter a new optimization problem, ask these questions in order:

  1. Can I write the objective and constraints as linear (or quadratic) expressions? If the relationships are highly nonlinear and can’t be linearized, MIP may not be the right starting point.

  2. How big is the problem? If you’re talking about billions of variables or an astronomically large feasible region, you probably need decomposition, heuristics, or a hybrid approach.

  3. How fast does the answer need to be? If it’s a weekly planning problem that can run overnight, MIP is great. If it’s a real-time system, you need something faster.

  4. How important is optimality vs. speed of development? For high-stakes decisions (supply allocation worth millions, network redesign), the investment in a proper MIP formulation pays off. For lower-stakes or rapidly changing problems, heuristics may be more practical.

  5. Is the data deterministic enough? If the dominant source of error is bad data or high uncertainty, the precision of MIP optimization may be wasted. Focus on the data pipeline and uncertainty modeling first.

The Hybrid Sweet Spot

In practice, the best systems often combine MIP with other approaches:

  • MIP + heuristics: Use a heuristic to generate a warm start, then let the solver improve it. Or use MIP for the strategic-level decisions and heuristics for the tactical details.
  • MIP + simulation: Optimize a plan with MIP, then stress-test it with simulation under hundreds of scenarios. If the plan is fragile, add robustness constraints and re-solve.
  • MIP + machine learning: Use ML to predict solver parameters, generate cuts, or approximate expensive subproblems. The solver handles the combinatorics; ML handles the pattern recognition.

The practitioners who get the most value from MILP are the ones who understand its boundaries. They don’t treat the solver as a magic box — they treat it as a precision instrument that works best when pointed at the right problem, with the right formulation, and the right expectations.

Master the tool. But master the judgment of when to use it even more.

Back to all lessons