Who plays how much? Squad minutes as a linear program

The football question

A season has 38 matches of 90 minutes, and a manager has to share them out. Some players are better than others, some can't play every game, and the club has its own rules, such as "our young players get at least 4,000 minutes between them." Who should play how much? And if the young players have to play, whose minutes should they take?

The concept

Linear programming solves problems where the objective and every rule are straight-line sums: so many goals per minute, so many minutes in total, at most so many for this player. The decision variables can take any value in between, such as 1,380 minutes rather than "picked" or "not picked". (Yes-or-no choices come later in this series, with integer programming.)

It was developed in the 1930s and 1940s for planning production and supplies, and George Dantzig's simplex method of 1947 made large problems solvable. When Dantzig showed his method to John von Neumann, von Neumann saw at once that it was the same mathematics as his work on zero-sum games, the minimax behind the penalty game.

The key fact about linear programs fits in one picture.

Two players first

An established striker is worth 0.12 goal difference per 90 minutes and a young striker 0.05 (made-up numbers). The rules:

• The established striker can manage at most 3,000 minutes, and the young one 3,420, every minute of the season.
• There are 5,000 minutes to share between them.
• The young one must play at least 1,500.

Each rule is a straight line, and together they fence off the feasible region: every split that obeys them all.

Because the objective is a straight-line sum too, moving across the region in any direction changes the goal difference at a steady rate. So you can always do at least as well by sliding to an edge, and then along the edge to a corner. The best answer to a linear program is always at a corner of the feasible region. Here there are only five corners to check, and the best is 3,000 minutes for the established striker and 2,000 for the young one: a goal difference of +5.1.

That's why linear programs can be solved quickly even when there are thousands of variables: a method only has to search the corners, and the simplex method moves from corner to better corner until none is better. Part 5 of this series works through it by hand.

The full squad

Here's a made-up squad of 14 outfield players for a 4-4-2. Each has a goal difference per 90 and a limit on the minutes he can manage:

The linear program is

$$\begin{aligned} \text{maximise } &\sum \text{per 90} \times \frac{\text{minutes}}{90} \\ \text{so that } &\text{every position is filled} \\ &\text{nobody passes his limit} \end{aligned}$$

With 14 variables, nobody draws the region. A solver searches its corners instead: scipy's linprog, in the snippet below.

Without the youth rule, the answer is what a manager would expect: the best player in each position plays as much as he can, then the next best, until the position is filled. The young players get only the minutes nobody better can cover, 2,220 between them. That breaks the club's 4,000 rule, so the rule is binding, as in Part 2.

With the rule, the young players play exactly 4,000 minutes. The solver finds the cheapest place to find the extra 1,780:

The extra minutes go first to the young midfielder, who's only a little worse than the player he replaces (0.05 against 0.06 per 90), then to the young defender, in place of the veteran (0.02 against 0.06). The young striker gets nothing extra, even though he's the best-rated of the three young players. Every minute he played would come from Striker 2, and the gap there (0.08 against 0.14) is the biggest. What matters isn't how good a young player is. It's how much worse he is than the player he'd replace.

The rule costs 0.42 goal difference over the season, out of +54.02 from the players without it.

The price of the rule

As in Part 2, the solver also reports a shadow price: what one more unit of the rule would cost. Here it's 0.44 goal difference for every extra 1,000 young minutes. That's the young defender's gap of 0.04 per 90 against the veteran, times 1,000 ÷ 90.

Shadow prices hold only for small changes. Re-solving with a 5,000-minute rule costs 0.51 more, not 0.44, because after 720 more minutes the veteran has none left to give up, and the young defender starts taking the right-back's minutes instead (a gap of 0.06). The price rises as the rule tightens, the same pattern as the chairman's goals rule in Part 2.

Why it matters

Squad rotation, youth development, travel plans, wage budgets: most club planning shares out something limited under rules, and much of it is linear, or close enough. A linear program finds the best split and, just as usefully, says what each rule costs and where the cost falls. A club that wants its young players to play can then decide where those minutes should come from, and how much it's paying, instead of finding out in May. Part 5 opens up the solver: the simplex method, by hand.

Limitations

• The squad is made up, and real players' value per 90 is hard to measure and changes with form and partners.
• Straight lines are an approximation. A player's value doesn't really stay the same from his first minute to his 3,000th; fatigue bends the line.
• Minutes aren't freely divisible. Real minutes come in matches and substitutions, and a player rested for one game is a yes-or-no choice. That's integer programming, later in the series.
• Young players' development isn't in the objective. The rule exists because the club values something the season's goal difference doesn't count. The shadow price says what that value has to be worth for the rule to pay.

Try it yourself

Before running the code, guess: if the young striker were worth 0.12 per 90 instead of 0.08, would he get any of the extra minutes? Then change his number and see. (Hint: compare him with the player he'd replace.)

Reproduce the analysis

This needs scipy (pip install scipy). It finds the two-player corners by working out where every pair of rule lines cross, then solves the full squad with and without the rule. All the numbers are made up.

from itertools import combinations

from scipy.optimize import linprog

# Two players first (made up): an established striker (x minutes) and a young one (y minutes), worth 0.12 and 0.05
# goal difference per 90. Each rule is a straight line a*x + b*y <= c.
rules = [(1, 0, 3000),       # the established striker can manage 3,000 minutes
         (0, 1, 3420),       # the young one, every minute of a 38-game season
         (1, 1, 5000),       # 5,000 minutes between them
         (0, -1, -1500),     # the young one plays at least 1,500 (written as -y <= -1500)
         (-1, 0, 0)]         # nobody plays negative minutes
value = lambda x, y: (0.12 * x + 0.05 * y) / 90

corners = set()
for (a1, b1, c1), (a2, b2, c2) in combinations(rules, 2):   # a corner is where two rule lines cross...
    det = a1 * b2 - a2 * b1
    if det:
        x, y = (c1 * b2 - c2 * b1) / det, (a1 * c2 - a2 * c1) / det
        if all(a * x + b * y <= c + 1e-9 for a, b, c in rules):   # ...and every other rule still holds
            corners.add((round(x), round(y)))
for x, y in sorted(corners):
    print(f"Corner: {x:5} and {y:5} minutes, goal difference {value(x, y):+.2f}")
print("Best corner:", max(corners, key=lambda c: value(*c)))

# The squad (made up): position, goal difference per 90, most minutes he can manage, young or not.
squad = {"Centre-back 1": ("DEF", 0.20, 3200, False), "Centre-back 2": ("DEF", 0.12, 3000, False),
         "Left-back": ("DEF", 0.10, 3100, False), "Right-back": ("DEF", 0.08, 3000, False),
         "Veteran defender": ("DEF", 0.06, 2000, False), "Young defender": ("DEF", 0.02, 2500, True),
         "Midfielder 1": ("MID", 0.25, 3300, False), "Midfielder 2": ("MID", 0.15, 3200, False),
         "Midfielder 3": ("MID", 0.10, 3000, False), "Midfielder 4": ("MID", 0.06, 2800, False),
         "Young midfielder": ("MID", 0.05, 2500, True),
         "Striker 1": ("FWD", 0.30, 3000, False), "Striker 2": ("FWD", 0.14, 3000, False),
         "Young striker": ("FWD", 0.08, 2500, True)}
needed = {"DEF": 4 * 3420, "MID": 4 * 3420, "FWD": 2 * 3420}   # 4-4-2 for 38 games of 90 minutes
names = list(squad)


def solve(young_minutes):
    """Best minutes for each player, with at least `young_minutes` for the young players between them."""
    c = [-squad[n][1] / 90 for n in names]                         # linprog minimises, so flip the sign
    a_eq = [[1 if squad[n][0] == pos else 0 for n in names] for pos in needed]
    a_ub = [[-1 if squad[n][3] else 0 for n in names]]             # -(young minutes) <= -young_minutes
    res = linprog(c, A_ub=a_ub, b_ub=[-young_minutes], A_eq=a_eq, b_eq=list(needed.values()),
                  bounds=[(0, squad[n][2]) for n in names], method="highs")
    return res, -res.fun


free, gd_free = solve(0)
ruled, gd_rule = solve(4000)
print()
print("Minutes, without and with the rule of 4,000 for the young players:")
for i, n in enumerate(names):
    print(f"  {n:<17}{free.x[i]:6.0f}{ruled.x[i]:7.0f}")
young = lambda res: sum(res.x[i] for i, n in enumerate(names) if squad[n][3])
print(f"Young players' minutes: {young(free):.0f} without the rule, {young(ruled):.0f} with it")
print(f"Goal difference from the players: {gd_free:+.2f} without the rule, {gd_rule:+.2f} with it; "
      f"the rule costs {gd_free - gd_rule:.2f}")
price = -ruled.ineqlin.marginals[0]   # the solver's shadow price for the rule, per minute
print(f"Shadow price: {price * 1000:.2f} goal difference for every 1,000 young minutes required")
print(f"Check, re-solving with 1,000 more: {gd_rule - solve(5000)[1]:.2f}")

It prints:

Corner:     0 and  1500 minutes, goal difference +0.83
Corner:     0 and  3420 minutes, goal difference +1.90
Corner:  1580 and  3420 minutes, goal difference +4.01
Corner:  3000 and  1500 minutes, goal difference +4.83
Corner:  3000 and  2000 minutes, goal difference +5.11
Best corner: (3000, 2000)

Minutes, without and with the rule of 4,000 for the young players:
  Centre-back 1      3200   3200
  Centre-back 2      3000   3000
  Left-back          3100   3100
  Right-back         3000   3000
  Veteran defender   1380    720
  Young defender        0    660
  Midfielder 1       3300   3300
  Midfielder 2       3200   3200
  Midfielder 3       3000   3000
  Midfielder 4       2800   1680
  Young midfielder   1380   2500
  Striker 1          3000   3000
  Striker 2          3000   3000
  Young striker       840    840
Young players' minutes: 2220 without the rule, 4000 with it
Goal difference from the players: +54.02 without the rule, +53.60 with it; the rule costs 0.42
Shadow price: 0.44 goal difference for every 1,000 young minutes required
Check, re-solving with 1,000 more: 0.51

linprog minimises, so the snippet hands it minus the goal difference and flips the signs back. The shadow price comes from the solver's marginals (in recent versions of scipy); the last line checks it by solving again.

Further reading

• Linear programming, Wikipedia. The method, its history from Kantorovich and Dantzig, and duality.
• scipy.optimize.linprog, the SciPy documentation for the solver used here.
• Shadow price, Wikipedia. What a constraint is worth, as in Part 2.