Generator

The vertex that maximises 3x₁ + 4x₂

A generator in the applied library, called 43 times across 9 essays. Below: what it draws at its defaults and at each mode an essay asks for, what it checks while drawing, and everywhere it is used.

polytope is one function. Everything below came out of it during this build, at parameters taken from the essays rather than invented for this page — so a figure here is the same figure a reader meets in an essay, and if the generator changes, this page changes with it.

At its defaults

The vertex that maximises 3x₁ + 4x₂. A two-variable linear program's feasible region, drawn from the exact intersection of every pair of its constraints, with the objective's contour lines and the optimal vertex marked.

`show: "birkhoff"`

A table of shares written as a lottery over 3 whole assignments. A doubly stochastic table of shares, and beneath it the permutation matrices and weights that add up to it exactly, each drawn as a grid with one marked cell per row.

`show: "extreme"`

`show: "support"`

`show: "primal"`

`show: "hungarian"`

A cheapest assignment, and the proof that it is cheapest. A 4 by 4 cost table with the cheapest assignment marked, and a row price and column price beside each. Every used cell's two prices add to its cost, and the prices total the assignment's cost.

What it checks while it draws

Collected by running the family and recording what it asserted, not written here. The count is how many separate times the claim was put to the test while these drawings were made.

the program at b₂ = 2 has at least one feasible vertex ×33
the program at b₂ = 2 is bounded — an objective that increases without limit has no optimal vertex to draw ×33
the program at b₂ = 5/2 has at least one feasible vertex ×32
the program at b₂ = 5/2 is bounded — an objective that increases without limit has no optimal vertex to draw ×32
the program at b₁ = 2 has at least one feasible vertex ×31
the program at b₁ = 2 is bounded — an objective that increases without limit has no optimal vertex to draw ×31
the program at b₁ = 5/2 has at least one feasible vertex ×30
the program at b₁ = 5/2 is bounded — an objective that increases without limit has no optimal vertex to draw ×30
the weights on person 1's task 1 add back to the share ×16
round 1: what is left still has a whole assignment inside it ×5
person 1's shares add to a whole task ×4
task 1 is exactly covered ×4
constraint row 1 constrains at least one variable ×3
constraint row 1 has one coefficient per variable ×3
the decomposition needs at most n² − 2n + 2 = 5 whole assignments ×2
the right-hand side is a list of 2 to 2 numbers ×2
a program here has between two and five constraint rows ×1
a rational is a whole numerator over a non-zero whole denominator ×1
a rational is never divided by zero ×1
a set of prices whose total equals the cheapest assignment exists ×1
an intersection is kept exactly when it satisfies every constraint ×1
and every corner is a whole assignment ×1
and every pair the assignment uses is tight ×1
and its weights add to one ×1
and the fractional corner is a half on every edge ×1
and the weight taken out is positive ×1
between three and six edges ×1
each decomposition rebuilds every entry exactly ×1
each entry of the right-hand side is a whole number between 0 and 400 ×1
each piece's slope is the dual variable on that piece ×1
every complementary product is exactly zero ×1
every constraint coefficient is a whole number of size at most 40 ×1
every dual certificate at this optimum gives the same price for the swept constraint ×1
every feasible primal value is at most every feasible dual value ×1
every objective coefficient is a whole number of size at most 40 ×1
every pair of constraints was formed, not a selection of them ×1
every set of people is willing to take at least as many tasks as there are of them ×1
no dual variable and no reduced cost is negative ×1
no feasible lattice point beats the best vertex ×1
no pair's two prices exceed its cost ×1
no share is negative ×1
no slack and no variable is negative at the optimum ×1
so a mixture containing it would give a share to a pairing the corner refuses ×1
so its total is half the number of edges ×1
so the prices add to the cheapest assignment's cost, which certifies it ×1
some order gives a genuinely different decomposition of the same table ×1
the constraint whose right-hand side is swept is a whole number between 1 and 2 ×1
the corners number the permutations, and no more ×1
the cost table is square ×1
the drawn dual region is convex ×1
the drawn primal region is convex ×1
the dual certificate is worth exactly what the primal optimum is worth ×1
the dual is drawn only for a program with two constraints — with more, the dual polytope has more than two variables and is not a polygon in the plane ×1
the dual optimum is unique, so each constraint has one price — a degenerate optimum, with more than two constraints through one point, has a whole set of them and no single table of products ×1
the dual program has at least one feasible vertex ×1
the dual program is bounded — an objective that increases without limit has no optimal vertex to draw ×1
the exact arithmetic stays inside the safe integer range ×1
the exact optimum and the decimal one agree ×1
the exact optimum at the top of the sweep and the decimal one agree ×1
the feasible vertices are in convex position ×1
the first order decomposes the table completely ×1
the fractional table needs at least two whole assignments ×1
the grid holds more matrices than there are permutations ×1
the grid the search runs on is a whole number between 3 and 8 ×1
the high end of the sweep is a whole number between 1 and 400 ×1
the low end of the sweep is a whole number between 0 and 400 ×1
the multipliers reproduce the objective exactly ×1
the number of people is a whole number between 2 and 4 ×1
the objective has one coefficient per variable ×1
the objective is not identically zero ×1
the optimal vertex has a dual certificate — a non-negative multiplier on each binding constraint ×1
the optimal vertex's coordinates are labelled clear of every dot, every value and the axis ticks ×1
the optimum has a dual certificate ×1
the optimum is linear across this interval, so the drawn segment is exact ×1
the polytope figure's mode is one of primal, dual, slack, shadow, birkhoff, extreme, support, assign, hungarian, lottery, fractional ×1
the primal maximum and the dual minimum are the same number ×1
the primal program has at least one feasible vertex ×1
the primal program is bounded — an objective that increases without limit has no optimal vertex to draw ×1
the reduced cost is the multiplier on the variable's own non-negativity ×1
the relaxation has a corner that is not whole ×1
the round empties at least one more cell than it found ×1
the share table is one of thirds, quarters, sparse ×1
the size of the assignment is a whole number between 2 and 4 ×1
the slope of the optimum equals the dual variable for the swept constraint ×1
the support contains a whole assignment ×1
the sweep produced at least one linear piece ×1
the sweep runs over between two and sixty units of the right-hand side ×1
the sweep solved the program once at every whole right-hand side ×1
the table is one the family knows ×1
the table is square ×1
the table is used up exactly ×1
the two optima agree as decimals too ×1
the weights add to one ×1
there are n! = 6 whole assignments ×1
there is one breakpoint between consecutive pieces ×1
there is one product per constraint and one per variable ×1
two different assignments differ somewhere ×1
weak duality was checked on the whole cross product of the two vertex lists ×1
which beats every whole matching, so the relaxation is genuinely loose ×1

Where it is called

Changing this generator changes every figure on this list. That is what makes the list worth publishing rather than keeping in a check script.

Applied

A lottery over whole assignments

A table of shares in which every person's shares add to one task and every task is exactly covered is never anything more than a mixture of whole assignments — and finding the mixture is a matter of taking one complete assignment out at a time.

Applied

A price for every person and task

The cheapest assignment can be found without comparing it to any other. Attach a number to each person and each task so that no pair's two numbers exceed its cost, and if the numbers add to an assignment's total, that assignment is cheapest — proved, by an argument that never mentions the alternatives.

Applied

A signal both can see

Two choosers who randomise privately can reach a set of outcomes that is smaller, and worse, than the set they reach when a device draws one cell and whispers each of them their half of it. Nothing is enforced and nobody is bound, and the arrangement is stable anyway.

Applied

A split nobody can walk away from

Every way of dividing what a group earns is a point of a triangle, and every coalition's threat to leave cuts a straight line across it. What survives all the cuts is the set of stable divisions — and for one three-player game there is nothing left.

Applied

One table, two lotteries

A table of shares says what fraction of each task each person does. It does not say how — the same table is a mixture of whole assignments in many different ways, and the differences are exactly what the people being assigned would care about.

Applied

The corners are whole assignments

A table of shares can be written as a lottery over whole assignments, which the anchor's first rung demonstrates on one example. The general statement is that the corners of the set of such tables are exactly the whole assignments, and that single fact is why the whole subject is easy.

Applied

Two numbers that have to meet

Every linear program has a shadow — a second program built from the same numbers read the other way, whose minimum can never fall below the first's maximum. That much is a one-line calculation; the theorem is that the two numbers are always exactly equal.

Applied

What a constraint is worth

The rung below settled that a linear program and its dual reach the same number. This one asks what the dual's variables are, and the answer converts a solution into a rate for every constraint — piecewise constant, zero on the constraints that are not doing any work.

Applied

Where the corners stop being whole

Everything on this ladder rests on one property — the relaxation of the assignment problem has whole-numbered corners. Add a single edge that closes an odd cycle and the property fails, a corner appears with a half in every coordinate, and the problem changes character completely.

The whole library · What the figures prove