Inside the solver: the simplex method by hand

The football question

In Part 4, a squad's minutes went into scipy and the best split came out, along with the price of the club's youth rule. What happened in between?

Part 4 also showed why there's a short cut: the best answer to a linear program is always at a corner. But big problems have a lot of corners. This part opens up the method that finds the best one without visiting them all.

The concept

George Dantzig's simplex method (1947) works like a manager improving a rota one change at a time:

1. Start at a corner. The simplest is nobody playing at all.
2. Look for the change that gains most. Of all the players who could be given more minutes, which adds the most goal difference per minute?
3. Give him minutes until a rule stops you. Either his own limit runs out or a shared limit does, whichever comes first. You've arrived at a new corner.
4. Repeat. When no change gains anything, you're at the best corner. Because the feasible region has no dents (all its rules are straight lines), a corner that no neighbouring move can improve is the best overall.

Each move from one corner to the next is called a pivot. The method keeps its working in a table (the "tableau"), but the logic is just those four steps.

By hand: two strikers

Take Part 4's two strikers, worth 0.12 and 0.05 goal difference per 90 minutes (made-up numbers). The rules: the established striker can play at most 3,000 minutes, the young one at most 3,420, and there are 5,000 between them. To start from nobody playing, leave out Part 4's minimum for the young striker. It didn't decide the answer there anyway.

Step 1. At the start, a minute for the established striker is worth 0.12 per 90 and a minute for the young one 0.05. The established striker gains most, so he gets minutes. Two rules limit him: his own 3,000 and the shared 5,000. His own runs out first, at 3,000.

Step 2. Now the only way to add minutes is to give them to the young striker, still worth 0.05 per 90. His own limit is 3,420, but only 2,000 of the shared 5,000 are left, so that rule runs out first, at 2,000.

Stop. Could any change still gain? More minutes for the established striker: no, he's at his limit. More for the young one: no, the 5,000 are used. Swapping a minute from the young striker to the established one is blocked by the established striker's limit. Nothing gains, so this is the best corner.

It's the same answer Part 4 found by checking all five corners: 3,000 and 2,000 minutes, +5.11. Here the method checked three.

The prices come free

The table the method keeps has a bottom row that says, for every possible change, how much it would gain. At the finish, that row holds something extra: the shadow price of every rule, as in Part 2 and Part 4, without solving anything again.

For the established striker's limit, the bottom row reads

$$\begin{aligned} &\text{gain per 90 more minutes} \\ &= 0.12 - 0.05 = 0.07 \end{aligned}$$

This is the reason solvers report shadow prices so readily. They're not an extra calculation; they're what the bottom row says when the method stops.

Why it's fast

Two strikers have five corners, so checking them all is easy. Now give 14 players their own limits (made-up numbers) and 34,200 minutes to share: ten outfield places for 38 games. That problem has 17,008 corners. The simplex method reaches the best one after visiting 13 of them.

To be fair, that problem is easy enough that sorting players from best to worst and filling their minutes in order would solve it too. The method earns its keep when rules overlap, as positions and the youth rule did in Part 4. Sorting can't handle those, but the simplex method still just moves from corner to better corner.

It isn't always this quick. The mathematicians Victor Klee and George Minty built a "squashed cube" on which the simplex method visits every single corner. But problems like that almost never come up in practice, where the method is remarkably efficient. That's why it's still at the heart of solvers like the one scipy used in Part 4, alongside newer methods.

Why it matters

Knowing what the solver does makes its answers easier to trust and explain. The answer is a corner, so some rules are always exactly at their limits, and those are the rules with a price. Every other rule has room to spare and a price of zero. When a club asks "what would it take to change the plan?", the shadow prices from the last step answer it. Part 6 of this series turns to choices that are yes or no, like signing a player, where the corners of a linear program no longer tell the whole story.

Limitations

• The numbers are made up, as in Part 4.
• The start has to be a corner. Here, no minutes for anyone is allowed. With Part 4's minimum for the young striker it isn't, and real solvers first find a starting corner, a step left out here.
• Ties and stalls. When two rules run out at the same moment, the method can stall at a corner for a while. Real solvers have rules to cope; this sketch doesn't need them.
• Rounding. Large problems run into rounding errors, which real solvers manage carefully.

Try it yourself

Before running the code: if the shared limit were 7,000 minutes instead of 5,000, which rule would stop step 2, and which rules would then have a price? Then change both 5000s to 7000 in the code and check.

Reproduce the analysis

This is the simplex method in about 30 lines of plain Python, printing each step. It solves the two strikers, checks the answer against every corner, then counts the 14-player problem's corners. Nothing to download, nothing to install.

from itertools import combinations


def simplex(values, rules, limits, names, rule_names, show=True):
    """Maximise sum(values[j] * x[j]) with sum(rules[i][j] * x[j]) <= limits[i] and every x >= 0, starting from
    all zeros. Each rule gets a 'slack': how much of it is still unused. Returns the answer, its value, the shadow
    price of each rule and the number of steps."""
    m, n = len(rules), len(values)
    table = [rules[i] + [int(i == k) for k in range(m)] + [limits[i]] for i in range(m)]
    gain = [-v for v in values] + [0] * m + [0]            # the bottom row: minus what one more unit of each adds
    basis = [n + i for i in range(m)]                     # at the start only the slacks are non-zero
    steps = 0
    while min(gain[:-1]) < -1e-12:
        enter = gain.index(min(gain[:-1]))                # the player who adds most per minute...
        room = [(table[i][-1] / table[i][enter], i) for i in range(m) if table[i][enter] > 1e-12]
        _, leave = min(room)                              # ...gets minutes until the first rule runs out
        p = table[leave][enter]
        table[leave] = [v / p for v in table[leave]]
        for i in range(m):
            if i != leave:
                f = table[i][enter]
                table[i] = [a - f * b for a, b in zip(table[i], table[leave])]
        f = gain[enter]
        gain = [a - f * b for a, b in zip(gain, table[leave])]
        steps += 1
        if show:
            print(f"Step {steps}: more minutes for {names[enter]}, until '{rule_names[basis[leave] - n]}' runs out")
        basis[leave] = enter
        if show:
            x = {names[j]: table[i][-1] for i, j in enumerate(basis) if j < n}
            print(f"  now {', '.join(f'{k} {v:,.0f}' for k, v in x.items())}; goal difference {gain[-1] / 90:+.2f}")
    x = [0.0] * n
    for i, j in enumerate(basis):
        if j < n:
            x[j] = table[i][-1]
    return x, gain[-1], gain[n:n + m], steps


# Part 4's two strikers (made up), without the young striker's minimum, so that zero minutes is a valid start.
names = ["the established striker", "the young striker"]
rule_names = ["established striker's limit", "young striker's limit", "5,000 between them"]
x, best, prices, steps = simplex([0.12, 0.05], [[1, 0], [0, 1], [1, 1]], [3000, 3420, 5000], names, rule_names)
print(f"Best: {x[0]:,.0f} and {x[1]:,.0f} minutes, goal difference {best / 90:+.2f}, in {steps} steps")
for r, p in zip(rule_names, prices):
    print(f"  Shadow price of '{r}': {p:.2f} goal difference per 90 extra minutes")

# A check: try every corner, as Part 4 did.
rules = [(1, 0, 3000), (0, 1, 3420), (1, 1, 5000), (-1, 0, 0), (0, -1, 0)]
corners = set()
for (a1, b1, c1), (a2, b2, c2) in combinations(rules, 2):
    det = a1 * b2 - a2 * b1
    if det:
        px, py = (c1 * b2 - c2 * b1) / det, (a1 * c2 - a2 * c1) / det
        if all(a * px + b * py <= c + 1e-9 for a, b, c in rules):
            corners.add((round(px), round(py)))
print(f"Check: {len(corners)} corners, best {max(corners, key=lambda c: 0.12 * c[0] + 0.05 * c[1])}")

# Bigger: 14 players (made up) sharing 34,200 minutes, ten places for 38 games, each up to his own limit.
values = [0.30, 0.25, 0.20, 0.15, 0.14, 0.12, 0.10, 0.10, 0.08, 0.08, 0.06, 0.06, 0.05, 0.02]
caps = [3000, 3300, 3200, 3200, 3000, 3000, 3100, 3000, 3000, 2500, 2800, 2000, 2500, 2500]
total = 34200
n = len(values)
rules = [[int(j == i) for j in range(n)] for i in range(n)] + [[1] * n]
_, best, _, steps = simplex(values, rules, caps + [total], [f"player {j + 1}" for j in range(n)],
                            [f"player {i + 1}'s limit" for i in range(n)] + ["34,200 in total"], show=False)

# Count every corner: each group of players at their limits with the rest on zero, if it fits in the total, and
# each point where the total cuts in, with one more player part-way.
count = 0
for k in range(n + 1):
    for group in combinations(range(n), k):
        used = sum(caps[j] for j in group)
        count += used <= total
        count += sum(used < total < used + caps[j] for j in range(n) if j not in group)
print(f"14 players: {count:,} corners; the simplex method visits {steps + 1} of them "
      f"(goal difference {best / 90:+.2f})")

It prints:

Step 1: more minutes for the established striker, until 'established striker's limit' runs out
  now the established striker 3,000; goal difference +4.00
Step 2: more minutes for the young striker, until '5,000 between them' runs out
  now the established striker 3,000, the young striker 2,000; goal difference +5.11
Best: 3,000 and 2,000 minutes, goal difference +5.11, in 2 steps
  Shadow price of 'established striker's limit': 0.07 goal difference per 90 extra minutes
  Shadow price of 'young striker's limit': 0.00 goal difference per 90 extra minutes
  Shadow price of '5,000 between them': 0.05 goal difference per 90 extra minutes
Check: 5 corners, best (3000, 2000)
14 players: 17,008 corners; the simplex method visits 13 of them (goal difference +54.54)

The bottom row of the table is kept in "per 90" units, so a shadow price of 0.07 means 0.07 goal difference for every 90 extra minutes the rule allowed.

Further reading

• Simplex algorithm, Wikipedia. The method in full, including the tableau and how solvers find a starting corner.
• Klee–Minty cube, Wikipedia. The problem on which the simplex method visits every corner.
• Linear programming, Wikipedia. Dantzig, von Neumann and the history from Part 4.