What solvers actually do

What is inside the box, and how to pick one you can actually deploy.

Take a small production model. Three products, two periods, twenty rows and twenty-one columns. Nothing about it is clever — it is the kind of thing you get on a first pass, written the way the problem was described to you.

Hand it to a solver, and before any algorithm you have heard of gets to run, the solver deletes most of it.

Thirteen of the twenty rows: gone. Twelve of the twenty-one columns: gone. And one of the yes/no decisions in it — a genuine decision, whether to set up a production line — is settled outright, by arithmetic, before the search opens a single node.

That is two thirds of the model, removed by something that is not the simplex method and is not branch and bound. It happens before either one is allowed to start. It is where a large part of the difference between solvers lives.

And it is almost never the part anybody learns.

This guide is in two halves. The first is that machinery, built and run in exact arithmetic so you can watch it work. The second is the part people actually get stuck on: which solvers exist, how they differ, which ones you can put in a container without a licence server ruining your week, and what the public benchmarks can and cannot tell you.

The plan. Chapters 1 to 5 are what a solver does before it solves anything, and what that costs. Chapter 6 is the rest of the machine. Chapters 7 to 13 are the landscape: who is who, what a modelling layer is, why the benchmarks are harder to read than they look, and licensing. Chapter 14 is how to choose.

Every number in the first half is computed by the code in this folder, in exact rational arithmetic, and asserted by a test. The second half is mostly not computable: it is claims about products and licences, which change. Those are dated, sourced, and kept to the things that have stayed true for years.

0What this is

Three words first, because the whole guide is written in them.

A model is a problem handed to a computer: a list of quantities to be decided, and a list of arithmetic rules those quantities must satisfy. Write it out as a grid, with one row per rule, one column per quantity, and a mark in a square wherever that quantity appears in that rule, and you get the picture above. So a row is a rule, a column is a quantity to be decided, and the marks are what people call the nonzeros. Almost every square is empty, which is why models get drawn this way: real ones are overwhelmingly empty, and that emptiness is what makes them solvable at all.

The model above is a small production plan: three products, two periods, 20 rules, 21 quantities and 42 marks.

Watch what survives. 20 rows, 21 columns and 42 nonzeros become 7, 9 and 14. Two thirds of the model is deleted before any solving starts, and the answer does not change: both versions cost $290, and an answer to the small model can be turned back into an answer to the big one exactly.

Here is one of the deletions, so that nothing about this looks like magic. One of the twenty rules says that the stock of product A at the start is zero. It arrived written as a rule because that is what was convenient to type, but it does not really describe how quantities interact. It is a fact about one quantity. So the solver copies "fixed at zero" onto that column and deletes the row; the model is one rule smaller and means exactly the same thing. And now that the quantity is pinned, it substitutes zero everywhere that column appears and deletes the column too. Two deletions, no cleverness, no risk.

This is presolve. Every serious solver does it, they all do it differently, and it is one of the main reasons that two solvers running "the same algorithm" are nowhere near the same speed.

In one sentence. Most of a model is usually redundant, and finding out which part is a separate job from solving it.

1A solver is not an algorithm

If you have read the other guides here, you already know how to solve a linear program: walk the corners, or go through the middle. You could implement one yourself in a few hundred lines, and people do.

And you would not have a solver. Not a rough one — a different kind of object.

What you would have is not a solver, and the gap is not a matter of polish.

A commercial mixed-integer solver is perhaps a million lines. The part that takes a step, the simplex pivot or the interior point iteration, is a small fraction of it. The rest is:

The last row is the one in the textbooks, and it is rarely where the difference between a solver that finishes and one that does not lives.

There is a well-known measurement of this. Robert Bixby tracked linear programming speed from 1988 to 2004 and separated the two causes: machines got about sixteen hundred times faster, and the algorithms and implementations got about 3,300 times faster on top of that. Thorsten Koch and colleagues repeated the exercise for 2001 to 2020 and found the machine-independent factor had continued to climb, more slowly for LP and considerably faster for mixed-integer problems.

Machine-independent means exactly what it says. Same computer, same model, same answer, thousands of times sooner, because of what the software decided to do before and around the arithmetic.

In one sentence. The algorithm is the part you can write down, and it is a minority of what makes a solver fast.

2What presolve takes out

Here is the model the animation was showing. Three products, two periods. For each product and period there is how much to make, how much to hold at the end of the period, and a yes/no switch for whether the line is open.

Demand is 40 units of A in period 2 and nothing in period 1, 25 units of B in each period, and nothing at all for product C, which is on the sheet because it is on the product list, not because anyone ordered it.

Every reduction below is something a person reading that model would notice. The model, as handed over, cannot notice any of it.

A row with one variable in it is a bound wearing a costume. holdA0 = 0 is not really a constraint. It is a fact about a variable. Presolve reads it as 0 ≤ holdA0 ≤ 0, writes that on the column, and deletes the row. Six rows go this way immediately, one for each product's opening and closing stock.

A variable whose two bounds have met is not a variable. holdA0 now has a lower bound of 0 and an upper bound of 0. There is nothing left to decide. Presolve substitutes the value into every row that mentions it and removes the column. Six columns go.

A row already at its limit forces everything in it. Product C's balance row in period 2 now reads holdC1 + makeC2 − holdC2 = 0, with holdC2 fixed at zero and the other two unable to go below zero. The smallest the left side can be is zero, and zero is exactly what it must equal. So every variable in that row is pinned at the only value that works. Nobody ordered any C, so nobody makes any C, and now the model knows.

A row that cannot be violated is not a constraint. The capacity row for period 2 allows 100 units. After the reductions above, the most that the surviving variables can add up to in that row is less than 100, whatever they do. The row can never bite. It is deleted.

A row can also just narrow a variable. The balance row for A in period 2 says holdA1 + makeA2 = 40. Both are at or above zero, so neither can exceed 40. Nothing is fixed and nothing is deleted, but two columns are now boxed in, and that turns out to matter enormously two chapters from here.

Whole numbers round. If a variable has to be an integer and its bounds are now 0.25 and 0.75, there is no value left and the model is infeasible. If its bounds are 0.25 and 1, then it is really 1.

(The names are singleton row, fixed column, forcing row, redundant row, bound tightening and integer rounding. Real solvers run dozens more, including ones that spot two rows saying the same thing and ones that prove a variable can be moved to a bound without loss.)

In one sentence. Each reduction is something obvious, and the model as written has no way to see any of them.

3The cascade, and where the gap opens

Take those reductions one at a time and they are unremarkable. Every one of them is something a careful person would spot. Run them in a loop, though, and something happens that no single pass could produce.

If presolve were a checklist applied once, those lines would fall in round one and go flat. They do not. The small model needs 3 rounds to settle, and the larger one needs 6.

The reason is that each reduction is what makes the next one visible. Deleting a row creates a fixed column. Fixing a column empties a row. Emptying a row narrows a bound. Narrowing a bound fixes another column.

None of those steps is clever. What is doing the work is the loop: a reduction that was invisible in round one becomes obvious in round three, because two rounds of other reductions have cleared the view. That is why presolve is described as a fixed point rather than a pass, and why a solver keeps going until a whole round changes nothing.

The count also grows with the model. Three rounds on twenty rows, six on a hundred and eighteen, and the depth is a property of how the reductions chain together rather than of how many there are.

It is also why two solvers with the same list of reductions can end up with models of different sizes. Run them in a different order and you reach a different fixed point.

In one sentence. Presolve is a loop rather than a checklist, because each reduction is what exposes the next one.

4A decision made by arithmetic

The best thing in this guide happens in round 3, and it is not a deletion.

Everything so far has deleted rows and columns, useful bookkeeping and nothing more. What happens in round 3 is the loop settling one of the actual decisions in the model, the kind a person would assume requires a search.

Product B needs 25 units in period 1. The balance row therefore forces makeB1 ≥ 25. The link row says makeB1 − 100 × openB1 ≤ 0, so

openB1 ≥ makeB1 / 100 ≥ 25 / 100 = 0.25

and openB1 is a yes/no switch, so it is a whole number. The smallest whole number at or above 0.25 is 1.

The setup happens. Not "probably happens", not "happens in the best solution found so far". It is forced, it is proved, and it is proved by division and rounding, before branch and bound has opened a single node.

That is four lines of arithmetic you can check by hand, and it disposes of a binary decision permanently. A search would have had to try both branches and prove one of them worthless.

Try it yourself → Move demand and the big-M constant, and watch the switch stop being a decision.

Now the part that turns this into advice. Look at what the deduction leaned on: the 100 in the link row, which is there only to mean "no limit, really". Make it 1,000,000 instead and the same chain gives openB1 ≥ 0.000025, which still rounds to 1, so this particular deduction survives.

But look at what happens to the fractional relaxation of that row. At 100, a model that wants to make 25 units must set openB1 to at least 0.25 and pay a quarter of the setup cost. At 1,000,000 it need only set it to 0.000025 and pays essentially nothing, so the relaxation happily makes things in a factory it has not paid to open. The bound it reports is correspondingly useless.

That is why "just use a big number" is the most expensive habit in integer modelling. The constant does not change what is feasible. It changes how much the relaxation is allowed to lie, and the relaxation is what prunes the tree.

In one sentence. A loop of obvious steps can settle a yes/no decision by division and rounding, and how big you made your big-M decides how much that kind of reasoning is worth.

5What it costs you

The reductions above changed the shape of the model. They also changed what the model can prove about itself, and that is the part that pays.

First, how a solver knows anything about the answer before it has found it. Cross out the requirement that the yes/no decisions be whole numbers, allowing a production line to be 0.25 open, and solve what is left. That is called the relaxation, and it is easy to solve. Because crossing out a requirement can only make things cheaper, whatever the relaxation costs is a floor under the true answer, a number the real answer cannot go below. The closer that floor is to the truth, the more of the search can be skipped.

The model as written has a relaxation costing $248, so the answer cannot be cheaper than $248. After presolve, the same relaxation costs $263, so now the answer cannot be cheaper than $263. The true answer is $290.

No cutting plane was added. No node was explored. $15 of a $42 gap closed, purely from columns being fixed and bounds being narrowed, and a better bound is worth more than a faster pivot, because it prunes the tree rather than walking it. On this instance branch and bound opens 9 nodes on the model as written and 5 on the reduced one. Small numbers, because it is a small model; the mechanism is what scales.

So much for the upside. Now the bill.

Your variables stop existing. Ask the solver for the value of holdA0 and it may not have one, because that column was gone before the algorithm started. This is what postsolve is for: it walks the reductions backwards and rebuilds a solution to the model you handed over. Every solver does this, and it is why you get your variable back. But if you are reading the internal model, or attaching callbacks to it, you are working with something that no longer matches what you wrote.

Sensitivity information gets harder. Shadow prices and ranges, the subject of the duality guide, are attached to rows. When a row has been deleted as redundant, the price that comes back for it is zero, which is correct and often not what the person asking wanted to know. Some solvers restrict presolve automatically when you ask for a sensitivity report, and it is worth knowing whether yours does.

"Presolve says infeasible" is a real answer and an unhelpful one. If the reductions prove there is no solution, you get told at once, which is fast and correct. What you do not get is a nice explanation, because the reasoning is a chain of reductions three rounds deep, each one resting on the last. Most solvers have a separate and much slower mode that will find a small conflicting subset of rows for you, and it is worth finding that flag before you need it.

And it is occasionally slower. On a model with little redundancy, presolve costs time and returns nothing. Rarely, it removes structure that a later part of the solver would have exploited. This is uncommon enough that leaving it on is the right default, and the flag to turn it off is nonetheless the first thing to reach for when a solver behaves inexplicably, because it tells you which half of the machine to suspect.

In one sentence. Presolve buys a stronger bound and a smaller model, and charges you in traceability.

6The rest of the machine

Presolve is the part this guide can compute. It is not the only part, and for mixed-integer problems it is not the largest.

Cutting planes are extra constraints that are true of every whole-number solution but false for the fractional answer the relaxation just produced. Add enough and the relaxation stops being able to lie to you. A modern solver generates a dozen families of them, adds far more than it keeps, and spends real effort deciding which to throw away, because a cut that does not tighten the bound is a row you now have to carry.

Heuristics try to find a decent solution early, by rounding, by fixing things and re-solving, by taking two known solutions and searching between them. The value is not the solution. It is that a good incumbent lets the search prune whole subtrees, and a search with no incumbent prunes nothing.

Branching is the choice of what to split on. It is the single most studied knob in the subject, and the difference between a naive rule and a good one is routinely orders of magnitude in tree size, which the branch and price guide runs into directly.

Numerics is the unglamorous one. Real models arrive with capacities in the millions and yields around 0.0001, and the ratio between the largest and smallest number in your matrix is a better predictor of trouble than its size. Solvers scale the matrix to fight this. Every one of them has tolerances: a number below which a value counts as zero, a violation below which a constraint counts as satisfied. Those are policy rather than bugs, and two solvers disagreeing about whether your model is feasible is usually two policies disagreeing rather than one of them being broken.

This guide computes none of that, and quoting numbers for it would mean inventing them. What the chapter is for is the shape: when a solver is slow, the question "which of these is going wrong" is more useful than "is my model too big".

In one sentence. Bound quality, a good early solution and sane numerics decide most solves, and none of them is the algorithm.

7Who is who

The landscape splits cleanly, and the split is about money rather than mathematics.

The commercial solvers. Gurobi, IBM CPLEX, FICO Xpress, COPT and MOSEK. They are fast, they are supported, and on hard mixed-integer models the good ones remain ahead of everything free. They are also expensive, and priced per machine or per core in ways that interact badly with autoscaling. Every one of them has a free size-limited or academic tier.

The open-source solvers. These are the ones worth knowing:

Two changes here matter more than any benchmark. SCIP moved from an academic licence to Apache 2.0 at version 8.0.3, which turned it from something you could publish papers with into something you could ship. And HiGHS has become good enough to be the default answer for anyone who does not have a specific reason to pay, which was not true a decade ago.

The honest summary of the gap: for pure linear programs at ordinary sizes, the free solvers are close enough that the difference rarely decides anything. For hard mixed-integer models the commercial ones are still meaningfully ahead, and the harder your model, the more that is true.

In one sentence. HiGHS or SCIP unless you have a hard integer model and a budget, and the reasons to pay are narrower every year.

8A layer is not a solver

This is the distinction that causes the most confusion, and it is worth getting straight before you compare anything.

You write a model in something. That something is usually not a solver.

Modelling layers let you write a model once and send it to any of several engines: Pyomo, PuLP and python-mip in Python, JuMP in Julia, and the commercial languages AMPL and GAMS. Switching solvers becomes a one-line change, which is the strongest practical argument for using one: it makes the solver decision reversible.

So the first question about any name you are handed is which of the two it is. Get that wrong and you will compare a language with an engine and conclude something about neither.

In one sentence. You write a model in a layer and it is solved by an engine, and keeping those separate is what keeps the engine replaceable.

9When the problem is not linear

Everything named so far assumes your model is linear, or linear with some whole-number decisions in it. Plenty of real models are neither, and they fail at the door rather than solving slowly.

CVXPY is a layer too, and a different animal, because it is not aimed at linear and integer models at all. It is for convex optimisation, the larger family that linear programming sits inside. Write a portfolio problem with a risk term that squares, or a fitting problem with a penalty on the size of the answer, and none of that is linear, all of it is convex, and none of the solvers named so far will take it.

What makes CVXPY worth singling out is that it will not let you write nonsense. It carries a rule system, disciplined convex programming, which checks that what you typed is provably convex by construction rather than hoping. A squared error is convex, so it passes. Multiply two variables together and it refuses, because that expression is not convex and no amount of solver effort would make the answer trustworthy. Most modelling layers accept whatever you type and let something downstream fail later, usually by returning a local answer with no warning that it is local. CVXPY stops at the door.

That is the same instinct as the presolve in this guide reporting infeasible outright rather than handing back a half-reduced model, and it is the right instinct. A refusal you can read beats a number you cannot check.

Underneath, CVXPY rewrites your problem into a standard conic form and hands it to a solver built for that, which is a different set of names again: Clarabel, SCS and OSQP among the open ones, MOSEK among the commercial. It has used Clarabel as its default since version 1.5, having replaced ECOS, which had been the default for years and had known trouble with numerical stability at the edges. It will also drive HiGHS when what you wrote turns out to be an ordinary linear program.

The limit is the same as the strength. CVXPY wants convexity. If your problem really is not convex, or its difficulty lives in whole-number decisions rather than in curvature, this is the wrong tool and a MIP solver is the right one.

In one sentence. If your model has squares or norms in it, none of the solvers named so far will take it, and the layer that will also refuses to let you write something it cannot vouch for.

10What OR-Tools actually is

There is a third thing a name can refer to, and it causes more confusion than either of the first two, because it contains both.

Google OR-Tools is a toolkit. Inside it are Google's own engines, GLOP for linear programming and PDLP for very large ones, alongside wrappers that let it drive SCIP, HiGHS and the commercial solvers. "We used OR-Tools" does not say which engine solved anything.

The exception is CP-SAT, which is Google's own and is a different kind of machine altogether. It is a constraint programming solver built on a SAT engine: it works in whole numbers, learns clauses from the conflicts it hits, and does not lean on a linear relaxation the way a MIP solver does. It has won its category at the MiniZinc competition repeatedly. For scheduling, rostering and assignment, where the constraints are logical rather than numerical, it is often the right tool and it will beat an LP-based solver comfortably.

Its limits are the mirror image. It wants integers and bounded variables. Give it truly continuous quantities, or a model whose strength lives in its linear relaxation, and a MIP solver is the better answer.

In one sentence. "We used OR-Tools" names a toolkit rather than an engine, and the one engine in it worth choosing deliberately is CP-SAT.

11Why the benchmarks cannot be read straight

The obvious move is to look up which solver is fastest. The standard source is Hans Mittelmann's benchmark pages, which have run for years and are the closest thing this field has to a referee.

Then read the note at the top, and watch the leaderboard stop meaning what you assumed it meant.

Here is what that note says.

Results for IBM CPLEX and FICO Xpress were removed after those vendors objected, following the 2018 INFORMS annual meeting. Gurobi withdrew in August 2024. MindOpt followed in December 2024.

The pages remain valuable and the methodology was never the problem. What changed is that the leaderboard now shows the solvers that stayed, so an absence on it carries no information about a solver's speed, and reading the tables as a complete ranking will mislead you about exactly the products that cost money.

In one sentence. Most of the commercial field left the public benchmarks by request, so what those tables rank is who is willing to be ranked.

12Measure on your own models

Now suppose the tables were complete. Every solver, every version, perfectly refereed. They would still not answer your question, and this is the more important of the two problems, because no amount of tidying up fixes it.

A benchmark is a set of models, and yours is not in it.

Solver performance varies over instances by orders of magnitude: not by tens of percent but by factors of a thousand. A solver that wins on a shifted geometric mean over a public set can comfortably be the slower one on your particular model, because your model has structure that the set does not, and structure is what solvers exploit. The aggregate is a fact about the aggregate.

Which makes the actual advice short, and it is the only thing in this chapter worth remembering. Take ten instances that look like what you will really be solving, run every candidate on them with a fixed time limit, and compare. That measurement is worth more than every published table put together, because it is the only one measuring the thing you care about.

Two traps while you do it.

Compare like with like. A solver that returns a 0.01% gap has not done the same work as one that proved optimality, and the second is doing something much harder. Fix the gap tolerance across candidates before you time anything.

Solve each model more than once. Most solvers are deterministic only when their thread count is fixed. A concurrent run will give you different timings, and sometimes different optimal solutions, on repeat runs of the same input. If you measure once, you are partly measuring the weather.

In one sentence. The only benchmark that answers your question is ten of your own models with the tolerances pinned.

13The licence is the deployment problem

Nobody warns you about this part, and it is where most of the deployment pain actually is. The mathematics never fails on a Friday; the licence does.

A commercial solver has to check that you are allowed to run it, and how it checks is the whole story.

Node-locked. A file tied to one machine, usually by its MAC address or host ID. Fine on a laptop. Useless the moment your workload lives on machines that did not exist this morning, because the identity it is locked to is the thing your infrastructure keeps replacing.

Floating. A licence server on your network hands out tokens, and you pay for how many are checked out at once. This works, and it requires that every worker can reach that server, which turns a maths library into a piece of network architecture with a firewall rule and a single point of failure.

Cloud and container licensing. This is the modern answer and the reason the old pain has eased. Gurobi's Web License Service issues short-lived signed tokens to a container over the internet, renewed automatically, configured either by mounting a gurobi.lic file or by setting three environment variables: GRB_WLSACCESSID, GRB_WLSSECRET and GRB_LICENSEID. That last form is what makes a solver deployable on Kubernetes at all, because the credential becomes a secret like every other secret. The other vendors have their own equivalents.

If you have fought a solver licence in a container, this is almost certainly what you were fighting: a node-locked or floating scheme meeting an environment where machines are disposable and there is no stable host to lock to. The fix is generally not a cleverer Dockerfile. It is a different licence type.

Academic licences are genuinely generous and sharply restricted. They are free, they are usually full-strength, and they are for academic work. Using one for anything commercial breaches the terms, and "it was only a prototype" is not a defence anyone has enjoyed making. Note also that free tiers are commonly size-limited rather than time-limited, which means your model will work fine until it grows.

And the open-source ones have none of this. No licence server, no tokens, no node locking, no phone call when you scale to forty workers. pip install highspy and it runs. That is regularly the deciding advantage for a team that would otherwise be slightly better served by a commercial solver.

The practical rule: decide how you will deploy before you decide what to deploy. Solver choice is easy to reverse behind a modelling layer. A licensing model that does not fit your infrastructure is not.

In one sentence. Pick the licence type your deployment can live with first, because that constraint is harder to change than the solver.

14How to choose

The short version, in the order the questions actually arrive.

Three closing observations, and they are the ones to have been told first.

Modelling beats solver choice, usually by more than an order of magnitude. The chapters above are about a solver deleting two thirds of a model. A better formulation does not need deleting. If a solve is too slow, rewriting the model will usually buy you more than any solver will, and the big-M constant from chapter 4 is the first place to look.

Measure before you buy. The evaluation licences exist for this. Ten of your own instances, a fixed time limit, all candidates.

Keep the solver replaceable. Write through a layer, and the decision you make today stays cheap to revisit. Everything in chapters 7 to 13 changes: SCIP's licence changed, Gurobi left the benchmarks, and cuOpt went from proprietary to Apache 2.0. The one durable move is to not be welded to any of it.

In one sentence. Formulate well, measure on your own models, and keep the solver behind a layer so that none of this has to be decided permanently.

What the plain words are really called

Further reading

Bixby's A Brief History of Linear Programming Computation for where the speedups came from, and Koch and co-authors' Progress in Mathematical Programming Solvers from 2001 to 2020 for the same exercise done again. Achterberg's thesis on SCIP is the most detailed public account of what is actually inside a MIP solver. Mittelmann's pages at plato.asu.edu/bench.html for benchmarks, read with chapters 11 and 12 in mind.

Product and licence details in chapters 7 to 13 were checked in August 2026. They are the parts of this guide most likely to date, which is why they are dated rather than stated flatly.

Running the code

make bootstrap    # once, from the repository root
cd solvers && make verify

The presolve here is exact rational arithmetic, which matters more than usual: in floating point, "this row can never be violated" quietly becomes "this row is violated by a millionth", and a reduction that fires on a rounding error deletes a real solution. The tests check every reduction against a brute-force enumeration of every whole point in the model, over four hundred random instances, because presolve is the part of a solver most capable of being confidently wrong.