What is operations research?

Operations research is the mathematics of deciding well under constraints. You write your limits down as inequalities, which carve out a feasible region of choices you could actually make; you write down what 'good' means as a single objective number; and the field's methods find the best point in that region and prove that nothing better exists. That proof of optimality, not just the answer, is what distinguishes it from a heuristic.

Why is the optimum of a linear program always at a corner?

Because the feasible region is convex. Any non-vertex feasible point can be written as a weighted blend of two other feasible points, and a weighted average of two objective values never exceeds the larger of them. So a non-vertex point is never strictly better than both of its neighbours, and you can always slide to an endpoint without losing anything. Repeating this argument lands you at a vertex, which is why an infinite search collapses into a finite one.

What is a shadow price?

A shadow price is the amount your objective would improve if you had one more unit of a given resource. It comes free with the solution as the dual variable for that constraint. Two consequences surprise people: a resource with slack has a shadow price of exactly zero, so buying more of it changes nothing; and relieving a bottleneck eventually destroys its own value, because once it stops binding its price collapses to zero. A shadow price is also only valid over a limited range of the right-hand side, so quoting one without its range tells half the truth.

Why is integer programming so much harder than linear programming?

Linear programming over the rationals is solvable in polynomial time and its optimum always sits at a vertex of a convex feasible region. Requiring variables to be whole numbers destroys that convexity and makes the problem NP-hard (Karp, 1972). The integer optimum can sit at a completely different vertex from the continuous one, so rounding the continuous answer is not a reliable strategy and can even produce an infeasible plan.

How does branch and bound solve problems too large to enumerate?

It never enumerates. It splits the problem into subproblems and, for each one, computes an optimistic bound by solving an easier relaxed version. If even that optimistic figure cannot beat the best solution already found, the entire subproblem is discarded without being searched, because the bound proves nothing inside it can win. Cuts near the top of the search tree eliminate exponentially more possibilities than cuts near the bottom, and finding a good solution early is what makes everything else prunable.

Why do queues explode before a system is fully utilised?

Because of variability. In the standard M/M/1 model the average time in the system - queueing plus service - is proportional to 1/(1-p) where p is utilisation, so it rises hyperbolically rather than linearly. Going from 50 percent to 80 percent utilisation multiplies it by 2.5 times, and going from 80 to 95 percent multiplies it by 4 times again. Queueing time on its own is proportional to p/(1-p) and rises faster still, by 4 times and then 4.75 times across the same two steps. Spare capacity is what absorbs random clumps of arrivals, so a system running near 100 percent has nothing left to absorb them with.

How does operations research connect to quantum computing?

Through five concrete bridges. First, QUBO and Ising formulations (Lucas, 2014) are the format quantum annealers and QAOA actually consume, so every quantum optimisation claim passes through them. Second, simulated annealing is the classical metaheuristic that quantum annealing imitates, and is the baseline any quantum claim must beat. Third, decoding the surface code in real time is solved as minimum-weight perfect matching using Edmonds' blossom algorithm from 1965, an operations research algorithm running as a component inside a quantum computer. Fourth, post-quantum security proofs are stated as games between a challenger and an adversary, the same minimax vocabulary game theory formalised for zero-sum games. Fifth, Goemans-Williamson's semidefinite relaxation of Max-Cut proves an unconditional 0.878567 for a classical algorithm, which is the number QAOA has to beat and, on the evidence verified for this page, has not yet beaten on general instances.

Operations research

The Feasible Region

Q: How is game theory different from the rest of operations research?

The rest of this course assumes one decision-maker facing fixed limits, with no second party reacting to the choice. Game theory covers what happens once another decision-maker is also choosing in response to you: your best move depends on theirs, which depends on yours, so there is no longer a single answer to compute -- only an equilibrium to find, a guaranteed value to prove, or a fair split to derive uniquely.

Everything that is actually possible. Nothing that isn't.

Operations research is the mathematics of deciding well when you cannot have everything. It routed your parcel, staffed tonight's hospital shift, and priced your flight twice while you were looking at it, and it is the field quantum computing is most often accused of being about to revolutionise. This is a course in it, from the top.

24topics, each built
picture → maths

2games where the
maths does the judging

1937the year it got its
name, at a radar station

3places it runs inside
a quantum computer

A black-and-white photograph of President Gerald Ford in a suit standing beside the seated mathematician George Dantzig, presenting him with a medal. — George Dantzig, who invented the simplex method in 1947, receiving the National Medal of Science from President Ford on 18 October 1976. Photograph: White House, Gerald R. Ford Presidential Library, a US government work in the public domain, source.

The whole field in four lines

1. You have a decision to make, and you can't do everything. There are limits on time, money, people, trucks, machines, beds.
2. Write the limits down as inequalities. The set of choices that satisfy all of them at once is the feasible region. Everything outside it is fantasy.
3. Write down what "good" means as a single number to push up or down. That's the objective.
4. Operations research finds the best point in that region, and proves that nothing better exists.

That last clause is the part people miss, and it is the entire reason the field matters. A heuristic gives you an answer. OR gives you an answer plus a certificate that no better answer exists.

Why this has its own front doorTwo reasons, and the second one is the interesting one

The first is that it already decides your day. This is not a niche academic discipline. It is the quiet infrastructure layer under logistics, energy, healthcare, manufacturing and finance, and it has been running there since the 1940s. Which route, which shift, which price, which warehouse, which power station at 6pm: all of it is somebody's objective function.

The second is that you cannot judge a quantum claim without it. When somebody says a quantum computer will "solve optimisation problems no classical computer can touch", this is the field they are making a claim about. You cannot evaluate that (you cannot even understand what is being asserted) without knowing what classical optimisation already does, how fast it already is, and where it genuinely struggles. Most quantum-optimisation hype survives entirely on the reader not knowing that a good solver will chew through a model with hundreds of thousands of variables before lunch.

So the honest order is: learn what the classical machinery does first. Then the quantum question becomes answerable instead of atmospheric. That is what this page is for, and why it sits beside the quantum material rather than inside it.

The course 33 topics, each taught four ways

Your progress: 0 of 33 understood

FoundationsRegions, corners and curves

Start with what a feasible region is (topic 01) and why the best point of a linear problem sits at one of its corners (02). Topic 16 is the algorithm that walks from corner to corner to find it, topic 03 shows that every such problem has a mirror problem whose answer is the price of each limit, and topic 17 lets the objective curve, ending at Goemans–Williamson's semidefinite relaxation of Max-Cut, the classical result that QAOA on the quantum side has to beat. Turn six of these shapes over in 3D →

01The feasible regionWhat does "optimising" actually mean? 02Linear programming and the vertex theoremWhy can you skip infinitely many points? 16The simplex algorithmHow do you actually find the best corner? 03Duality and shadow pricesWhere should the next rupee go? 17Quadratic & semidefinite programmingWhat does a quantum computer actually have to beat?

DiscreteWhen the answer must be whole, and when exact methods run out

Integer programming (topic 04) is where the corner theorem stops being enough, and branch and bound (05) is the machinery that copes. Topic 19 shares this course's language of variables and constraints but drops the objective: sometimes the honest question is not “what's best” but “does anything work at all.” Topic 21 asks when the simplest rule of thumb is provably good enough, and topic 10 is what you reach for once exact methods die.

04Integer programmingWhy is "whole numbers only" so expensive? 05Branch and boundHow do you search a space too big to search? 19Constraint satisfactionDoes a solution exist at all? 21Greedy algorithms & approximation guaranteesWhen is "take the best-looking option now" provably good enough? 10MetaheuristicsWhat do you do when proof is out of reach?

NetworksFlows, assignments and routes

Network flow and min-cut (topic 06), its special case the transportation problem (18), which keeps only two flat layers of nodes, matching and assignment (07), and shortest paths with dynamic programming (08): the structure real shipping, scheduling and routing problems have.

06Network flow and min-cutHow much can you push through a network? 18The transportation problemWhat happens when a flow network has no interior? 07Matching and assignmentHow do you pair things up without being greedy? 08Shortest paths and dynamic programmingWhy is the direct road not the fastest route?

UncertaintyDeciding when the world is not certain

Topic 08 solved the shortest path under a quiet assumption: choosing an edge means taking it. Topic 20 removes that assumption on the same network, and topic 22 removes the assumption that the numbers are known before you commit; the two honest ways to cope (average over what might happen, or armour against the worst of it) give different answers on the same problem. Topic 09 is the mathematics of waiting when arrivals and service are random.

20Markov decision processes & reinforcement learningWhat if the edge you choose isn't the edge you get? 22Stochastic & robust optimizationWhat do you optimise when the data isn't known yet? 09Queueing theoryWhy do systems collapse before they are full?

Many goals and playersWhen more than one objective, or more than one decision-maker, is involved

Topic 23 keeps one decision-maker but gives them several objectives that genuinely conflict, so “optimal” stops being a point and becomes a curve. Game theory (topics 11 to 15) drops the other assumption: when another party is also choosing in response to you, your best plan depends on theirs and there is no single answer to compute, only an equilibrium to find. It underwrites markets that clear through auctions, security proofs written as games between an adversary and a defender, and populations that settle into stable mixes of strategy.

23Multi-objective optimizationWhat is "best" when you can't improve one goal without hurting another? 11Nash equilibriumWhat happens when your best move depends on theirs? 12Zero-sum games and minimaxWhy does bluffing have to be random to work? 13Cooperative games and the Shapley valueIf a team earns money together, who earned how much of it? 14Mechanism design and auctionsCan you design the rules so honesty is the winning move? 15Evolutionary game theoryWhat happens when strategies reproduce instead of reasoning?

Games, part twoTime, secrets, repetition, learning, signals, traffic, hardness and a quantum game

Topics 11 to 15 asked who gains when several players choose. These nine go further: what changes when the moves come in turns (25), when players hold secrets (26), when they meet again (27), when they learn as they go (28), when a shared signal is allowed (29), when each chooses a route (30), when the question is how hard an equilibrium is to find (31), the one place where quantum physics changes a game's value (32), and then a market you design and attack yourself (33).

25Games over time: threats and backward inductionWhy does a threat that would hurt the threatener fail? 26Private information: auctions and Bayesian gamesHow much should you bid when you do not know what the others will pay? 27Repeated games: cooperation that lastsHow can selfish players keep cooperating when defecting pays today? 28Learning to play: regret and the minimax valueCan players who only look at their own past results end up playing the equilibrium? 29Correlated equilibrium: a traffic lightHow can a shared signal make two selfish drivers both better off? 30What selfishness costs: the price of anarchyHow much worse is everyone's trip when each driver chooses their own route? 31How hard is an equilibrium?If every game has an equilibrium, why is finding one hard? 32A game where physics changes the answer: CHSHCan sharing an entangled pair help two players win a game with no communication? 33Design a small market and break itWhich sale rule would you choose, and how would you attack it?

CapstoneInventory and supply chain

The course closes on the oldest applied problem in the field, the one Ford Whitman Harris wrote a formula for in 1913, and shows how many of the threads of this course meet inside a warehouse.

24Inventory & supply chainHow much to order, and when: the oldest formula in the field?

PlayTwo games where the mathematics does the judging

Neither can be won by feel. Both were built the way everything else here is: the answer was computed offline in exact arithmetic first, and the game only ever reports what that arithmetic says. Par is a proven number in both, but it means different things: in The Bottleneck it is the best score reachable, found by enumerating every purchase sequence, so you can hit it. In The Prune it is a floor (the count of branches that no strategy on earth could safely skip) and on the larger levels it is provably out of reach, which is why those levels are cleared against a measured target instead.

Game one · topic 03, made expensive

The Bottleneck

You have inherited a plant that is short of everything, and a board that will fund exactly one upgrade a quarter.

Game two · topic 05, at full scale

The Prune

Four thousand and ninety-six possible hauls. You will look at about thirty-five, and prove the rest cannot win.

The verdictCan quantum beat classical on optimisation?

The question has no answer in the abstract and a perfectly good one on a named instance. So here is a named instance (the same crates you just loaded) attacked five ways, with the column that almost every comparison leaves out: what each method can actually prove when it stops.

That column is the whole argument. A number without a certificate is a claim. Four of these five finish holding a claim, and one of the four is the quantum one.

Watch what happens as you move up the instances. On the first two, Grover’s query count sits below branch and bound’s node count, 6 against 14, then 18 against 27. Quantum genuinely wins those rows and the table says so plainly. The verdict flips at the third, where 50 queries meets 31 nodes, and by the fourth it is 201 against 29. Greedy, meanwhile, goes from exactly optimal to 23 short, and annealing stops without ever knowing which of those two it did.

It flips because the problem acquired structure, not because the quantum method got worse. Grover is doing precisely what it always does, and that is the point. Its speedup is quadratic but still exponential, and identical whether the haystack is a knapsack or pure noise, because it never reads the structure. The bound is made of that structure, so it barely grows at all.

This is the honest shape of nearly every quantum-optimisation claim you will read: true on an instance small enough that you did not need a quantum computer, and untested at the size where you would.

The overlapWhere this touches quantum computing: five real bridges

These are not analogies. Each is a place where the same mathematics is load-bearing on both sides.

QUBO and Ising

Nearly every combinatorial problem can be rewritten as minimising Σ w_ij s_i s_j over spins of ±1: the ground state of a magnet (Lucas, 2014). This is the format quantum annealers and QAOA actually consume, so it is the doorway every quantum optimisation claim has to walk through. Constraint satisfaction (topic 19) is a standing source of these instances: each violated constraint becomes an energy penalty, so satisfying every constraint becomes finding the ground state. It is also the format three real classical hardware families now consume directly: coupled oscillators, coupled lasers, and fluctuating bits, engineered to settle into that same ground state.

Play it. Graph City → Can classical hardware actually do this? →

Metaheuristics

Simulated annealing is the classical baseline that quantum annealing imitates. Knowing how well the classical version does is the only way to judge whether the quantum one is beating anything. See topic 10.

Play it. The Annealing Volcano →

Matching, inside the machine

The best one, and almost nobody says it out loud: a quantum computer's error correction runs in real time because of an operations research algorithm. Decoding the surface code is minimum-weight perfect matching. Edmonds, 1965. See topic 07.

Play it: the Decoder Duel →

Security games

Every post-quantum security proof on this site is stated as a game between a challenger and an adversary: exactly topic 12's minimax framing, used in earnest. "Secure" means no adversary's winning probability can be pushed above a negligible bound, whatever strategy they run.

See it on the PQC pages →

SDP vs. QAOA

The sharpest bridge of the five, because it is a head-to-head. Goemans–Williamson's SDP relaxation of Max-Cut (topic 17) proves an unconditional 0.878567 for a classical polynomial-time algorithm. QAOA was introduced on the same problem, and at its shallowest depth its own authors' bound sits below that number, not above it, with a later result showing a simple classical algorithm still matching or beating it one depth up. This is the honest, checkable version of "can quantum beat classical at optimisation", not the atmospheric one.

See it worked through: topic 17 →

QuestionsWhat people actually ask

Is operations research just applied maths, or a branch of computer science?

Historically neither. It began in pre-war Britain in 1937, when a group of scientists was asked not to improve radar but to work out how to use it well, and it expanded enormously once the war started two years later. It kept the habit of starting from a real operation rather than from a theorem. Today it overlaps heavily with combinatorial optimisation in computer science and with parts of economics and statistics, and the boundaries are not worth policing.

Is OR the same thing as machine learning?

No, and the distinction is useful. Machine learning mostly predicts: given data, what will happen? OR mostly decides: given what will happen, what should we do about it, subject to what we cannot change? Real systems chain them: forecast demand with ML, then decide inventory with OR. Topic 08 is where the two genuinely meet.

How is game theory different from the rest of this course?

Topics 01–10 all assume one decision-maker facing fixed limits: a machine-hour cap, a network, a queue. However hard the problem, there is one objective to optimise and the world does not react to your choice. Game theory (topics 11–15) is what you need the moment a second decision-maker is also choosing, in response to you: your best move now depends on theirs, which depends on yours, and there is no longer a single number to compute: only an equilibrium to find, a value to guarantee, or a fair split to prove unique.

Will quantum computers make this obsolete?

Not on any evidence currently available. Quantum optimisation is real research and worth watching, but there is no known quantum algorithm that beats a strong classical solver on a problem anyone actually needs solved, and the quadratic speedup that is proven for unstructured search does not apply to the structured problems where classical methods do their best work, as topic 05 shows. Anyone telling you otherwise should be asked for the resource estimate.

Do I need to be good at maths to start?

To understand the pictures and intuitions in this course, no: school algebra is genuinely enough, which is why every topic leads with a drawing. To write models professionally you need linear algebra and comfort with proofs. To invent new algorithms, considerably more. The first step is much smaller than people expect.

About How we check AI use Corrections Privacy Terms