£30m and five gaps: why you can't sign 0.83 of a centre-back

The football question

The club has £30m and five positions it wants to strengthen: centre-back, full-back, midfield, wing and up front. The scouts have five names for each. Which players should it sign?

Part 1 answered a smaller question by checking every combination of five players. Part 4 used a linear program to share out minutes, where any amount in between was fine. Signings are different: you sign a player or you don't. This part is about what happens when the answer has to be whole.

The concept

An integer programming problem is a linear program where some variables must be whole numbers, here 0 (don't sign) or 1 (sign). It looks like a small change. It isn't: the feasible region is no longer a shape with corners but a scattering of separate points, and the short cut from Parts 4 and 5 (the best answer is at a corner) no longer applies.

Solvers handle it by solving the easier version first: the same problem with the whole-number rule dropped, called the LP relaxation. Then they repair the answer using branch and bound, explained below.

A football example

Here's the made-up shortlist: five players per position, each with a fee and the points he'd add over a season, from cheapest to dearest.

Call them CB1 to CB5, FB1 to FB5 and so on, cheapest first. The rules: at most one signing per position, and £30m in total. With six choices for each position (one of five players, or nobody), there are 6 × 6 × 6 × 6 × 6 = 7,776 possible sets.

Each signing is a yes-or-no decision variable x, 1 if signed and 0 if not, and the problem is

$$\begin{aligned} \text{maximise } &\sum \text{points} \times x \\ \text{so that } &\sum \text{fee} \times x \le 30 \\ &\text{at most one per position} \\ &x = 0 \text{ or } 1 \end{aligned}$$

What the linear program says

Drop the whole-number rule and solve it as a linear program. The answer is worth 13.37 points, and it signs FB2, MF2, WG2 and ST3, plus 0.83 of CB1 and 0.17 of CB3.

That isn't a signing plan. And the obvious fixes don't work:

• Round down, dropping both part-centre-backs: FB2, MF2, WG2 and ST3 for £26m and 11.6 points, with £4m left unspent.
• Round up, signing both: £38m, £8m over budget, and two centre-backs when the rule allows one.

The best whole answer

Checking all 7,776 sets, and scipy's integer solver in the snippet, agree: sign CB1, FB2, MF2, WG2 and ST3. That's £29m for 13.0 points. The cheap centre-back (CB1) gets in whole, and £1m is left unspent, because no swap that uses it adds any points.

The relaxation's 13.37 is a ceiling no whole answer can reach. The gap between the ceiling and the real best (0.37 points here) is the price of not being able to sign part of a player.

Branch and bound

Checking 7,776 sets is quick for a computer. A real shortlist with 20 names for each of 8 positions has 21⁸, about 38 billion, and checking them all stops being practical. Branch and bound avoids it:

1. Solve the relaxation. If every player comes out whole, that's the answer.
2. If a player comes out part-signed, such as 0.83 of CB1, branch: make two smaller problems, one where he must be signed and one where he can't be.
3. Solve each branch's relaxation. Its answer is a ceiling for everything in that branch.
4. Bound: if a branch's ceiling is no better than the best whole answer found so far, throw the whole branch away without looking inside it.

Here branch and bound finds the 13.0-point answer after solving 35 small linear programs instead of checking 7,776 sets. The saving grows with the problem: the bigger the shortlist, the more of it gets thrown away unseen.

The staircase

Part 2 and Part 4 put a shadow price on a rule: what one more unit of it is worth. With whole players, the idea breaks.

Allow fractions and every extra £1m around £30m is worth about 0.37 points, smoothly. With whole players, the value comes in steps. £30m buys exactly what £29m does, but £29m buys 0.9 points more than £28m. At £28m the best set has no full-back (CB2, MF2, WG2, ST3); the extra £1m lets the club swap CB2 for the cheaper CB1 and add FB2. A club asking "what's another £1m worth?" gets a different answer at every budget: sometimes nothing, sometimes a lot.

Why it matters

Most club decisions are yes or no: sign him or not, play the cup tie with the first team or not, renew a contract or not. Treating them as fractions gives answers that look precise and can't be carried out, and rounding them can break the very rules you set. Integer programming respects that choices come whole, and branch and bound is why it can be solved in practice. The staircase is a warning for budget meetings: with whole players, the value of a little more money depends on exactly how much you already have. Part 7 looks at a yes-or-no problem with a special shape, pairing each marker with one attacker, that can be solved without branch and bound.

Limitations

• The shortlist is made up, and real points-added estimates are uncertain.
• Fees and points aren't fixed. Real fees are negotiated, and a player's value depends on who else is signed.
• One budget line is a simplification. Wages, contract length and resale all matter.
• Branch and bound can still be slow. In the worst case it explores a lot of branches. Real solvers add many tricks; this is the core idea.

Try it yourself

Give the club £31m instead of £30m. Before running the code, guess: does the plan change, and does the leftover £1m from the £30m plan help? Then add a sixth position, a goalkeeper, and see how the number of combinations, and branch and bound's count, change.

Reproduce the analysis

This needs scipy (pip install scipy). It checks every set, solves the linear program and rounds it both ways, solves the integer program with scipy's milp, runs a simple branch and bound, and prints the staircase. All the numbers are made up.

from itertools import product

import numpy as np
from scipy.optimize import Bounds, LinearConstraint, linprog, milp

# Made up: five positions to strengthen, five players on the shortlist for each, with a fee (£m) and the points
# he'd add over a season. Sign at most one per position, within the budget.
shortlist = {
    "Centre-back": [("CB1", 3, 1.4), ("CB2", 6, 2.2), ("CB3", 9, 3.6), ("CB4", 14, 4.4), ("CB5", 18, 5.2)],
    "Full-back":   [("FB1", 2, 0.6), ("FB2", 4, 1.7), ("FB3", 7, 2.4), ("FB4", 10, 3.5), ("FB5", 13, 3.9)],
    "Midfielder":  [("MF1", 4, 1.5), ("MF2", 6, 2.9), ("MF3", 10, 3.3), ("MF4", 13, 4.8), ("MF5", 17, 5.4)],
    "Winger":      [("WG1", 3, 1.0), ("WG2", 5, 2.3), ("WG3", 8, 2.8), ("WG4", 12, 4.6), ("WG5", 16, 5.0)],
    "Striker":     [("ST1", 5, 2.4), ("ST2", 8, 3.0), ("ST3", 11, 4.7), ("ST4", 15, 5.3), ("ST5", 21, 7.4)],
}
BUDGET = 30
players = [p for group in shortlist.values() for p in group]
fees = np.array([p[1] for p in players], float)
pts = np.array([p[2] for p in players], float)
one_each = np.array([[1 if p in group else 0 for p in players] for group in shortlist.values()])


def brute(budget):
    """Try every combination: one player or nobody for each position."""
    best, pick = 0.0, ()
    for combo in product(*[[None] + group for group in shortlist.values()]):
        chosen = [p for p in combo if p]
        if sum(p[1] for p in chosen) <= budget and sum(p[2] for p in chosen) > best + 1e-9:
            best, pick = sum(p[2] for p in chosen), tuple(p[0] for p in chosen)
    return best, pick


def relaxed(budget, fixed=None):
    """The linear program: any fraction of a player allowed. `fixed` pins some players to 0 or 1."""
    lo, hi = np.zeros(len(players)), np.ones(len(players))
    for i, v in (fixed or {}).items():
        lo[i] = hi[i] = v
    res = linprog(-pts, A_ub=np.vstack([fees, one_each]), b_ub=[budget] + [1] * len(shortlist),
                  bounds=list(zip(lo, hi)), method="highs")
    return (-res.fun, res.x) if res.status == 0 else (None, None)


combos = 1
for group in shortlist.values():
    combos *= len(group) + 1
best, pick = brute(BUDGET)
print(f"{combos:,} combinations; best by trying them all: {', '.join(pick)}, {best:.1f} points, "
      f"£{sum(p[1] for p in players if p[0] in pick)}m")

lp, x = relaxed(BUDGET)
print(f"Linear program: {lp:.2f} points, signing", ", ".join(f"{x[i]:.2f} of {p[0]}" for i, p in enumerate(players) if x[i] > 1e-6))
down = [p for i, p in enumerate(players) if x[i] > 1 - 1e-6]
up = [p for i, p in enumerate(players) if x[i] > 1e-6]
print(f"  Rounded down: {', '.join(p[0] for p in down)}, {sum(p[2] for p in down):.1f} points, £{sum(p[1] for p in down)}m")
print(f"  Rounded up:   {', '.join(p[0] for p in up)}, {sum(p[2] for p in up):.1f} points, £{sum(p[1] for p in up)}m")

res = milp(-pts, integrality=np.ones(len(players)), bounds=Bounds(0, 1),
           constraints=[LinearConstraint(fees, ub=BUDGET), LinearConstraint(one_each, ub=1)])
print(f"Integer program (scipy milp): {', '.join(p[0] for i, p in enumerate(players) if res.x[i] > 0.5)}, "
      f"{-res.fun:.1f} points")

# Branch and bound: solve the relaxed problem; if a player comes out fractional, split into "must sign him" and
# "can't sign him", and drop any branch whose relaxed best can't beat the best whole answer found so far.
found, explored = 0.0, 0
stack = [{}]
while stack:
    fixed = stack.pop()
    explored += 1
    value, x = relaxed(BUDGET, fixed)
    if value is None or value <= found + 1e-9:
        continue                                            # impossible, or can't beat what we have
    frac = [i for i in range(len(players)) if 1e-6 < x[i] < 1 - 1e-6]
    if not frac:
        found = value                                       # a whole answer, and the best so far
        continue
    stack += [{**fixed, frac[0]: 0}, {**fixed, frac[0]: 1}]
print(f"Branch and bound: {found:.1f} points after solving {explored} relaxed problems, not {combos:,}")

print()
print("Budget  whole players  fractions allowed")
for b in range(20, 41):
    print(f"  £{b}m  {brute(b)[0]:13.1f}  {relaxed(b)[0]:17.2f}")
for b in (28, 29):
    v, p = brute(b)
    print(f"Best for £{b}m: {', '.join(p)}, {v:.1f} points")

It prints:

7,776 combinations; best by trying them all: CB1, FB2, MF2, WG2, ST3, 13.0 points, £29m
Linear program: 13.37 points, signing 0.83 of CB1, 0.17 of CB3, 1.00 of FB2, 1.00 of MF2, 1.00 of WG2, 1.00 of ST3
  Rounded down: FB2, MF2, WG2, ST3, 11.6 points, £26m
  Rounded up:   CB1, CB3, FB2, MF2, WG2, ST3, 16.6 points, £38m
Integer program (scipy milp): CB1, FB2, MF2, WG2, ST3, 13.0 points
Branch and bound: 13.0 points after solving 35 relaxed problems, not 7,776

Budget  whole players  fractions allowed
  £20m            9.3               9.42
  £21m            9.6               9.85
  £22m            9.9              10.27
  £23m           10.7              10.70
  £24m           10.7              11.08
  £25m           11.3              11.47
  £26m           11.6              11.85
  £27m           11.9              12.23
  £28m           12.1              12.62
  £29m           13.0              13.00
  £30m           13.0              13.37
  £31m           13.5              13.73
  £32m           13.8              14.10
  £33m           14.1              14.47
  £34m           14.2              14.83
  £35m           15.2              15.20
  £36m           15.3              15.53
  £37m           15.3              15.86
  £38m           15.9              16.19
  £39m           16.1              16.51
  £40m           16.4              16.84
Best for £28m: CB2, MF2, WG2, ST3, 12.1 points
Best for £29m: CB1, FB2, MF2, WG2, ST3, 13.0 points

The branch and bound here always splits on the first part-signed player and explores the "can't sign him" branch last. Real solvers choose more cleverly, but the count shows the idea.

Further reading

• Integer programming, Wikipedia. The problem, the LP relaxation and the main methods.
• Branch and bound, Wikipedia. The method in general.
• Knapsack problem, Wikipedia. The classic version of this problem: the most value that fits in a fixed budget.
• scipy.optimize.milp, the SciPy documentation for the integer solver used here.