Loading a barbell with as few plates as possible

My local gym was closed to prevent the spread of coronavirus, but has finally reopened. To comply with guidelines and avoid transmitting germs, I would like to touch as few objects as possible while doing my workout. More precisely, I want to minimize the amount of plates I use at the gym, while still having enough plates to do all my work sets.

Does that sound like an optimization problem to you? It does to me! Let’s solve it.

Table of contents

A simple problem instance

Let’s study a concrete example before solving the general problem. The standard metric plates found in most gyms are

\begin{align} 1.25 \, \text{kg}, \, 2.5 \, \text{kg}, \, 5 \, \text{kg}, \, 10 \, \text{kg}, \, 15 \, \text{kg}, \, 20 \, \text{kg}, \, 25 \, \text{kg} \end{align}

If my works sets are done at \(W_1 = 100 \, \text{kg}\) and \(W_2 = 110 \, \text{kg}\), which plates should I choose? Let’s examine two feasible solutions.

Solution 1. The barbell weighs \(20 \, \text{kg}\), so I could use \(4 \times 20 \, \text{kg}\) plates and \(6 \times 15 \text{kg}\) plates, since

\begin{align} 100 &= 20 + (4) \times 20 \\ 110 &= 20 + (6) \times 15 \end{align}

This solution requires \(4 + 6 = 10\) plates in total. Not too bad, but we can do better.

Solution 2. A different solution would be to use \(4 \times 20 \, \text{kg}\) plates and \(2 \times 5 \, \text{kg}\) plates, since

\begin{align} 100 &= 20 + (4) \times 20 \\ 110 &= 20 + (4) \times 20 + (2) \times 5 \end{align}

This solution only requires \(4 + 2 = 6\) plates.

Clearly Solution 2 is better than Solution 1. Is it the best solution possible? How can we solve the general problem?

An Integer Program formulation

The general problem can be formulated as an Integer Program. We index the work sets by \(j\), and let \(W_j\) be the weight needed on the barbell for work set \(j\). We index the plate types by \(i\). Finally we denote the number of plates of type \(i\) used for work set \(j\) by \(x_{ij}\), and let \(w_i\) be the weight of plate \(i\). For instance, \(i=1\) might denote the \(1.25 \, \text{kg}\) plates, and a solution with \(x_{12} = 3\) would mean using \(3\) plates weighing \(1.25 \, \text{kg}\) on work set \(2\).

The Integer Program is given below. The first constraint says “for every work set \(j\), the total weight used must add up to the weight needed on the barbell for that set.” In the model below I have accounted for the weight of the barbell, which is \(20 \text{kg}\). Furthermore, the factor \(2\) enforces a symmetric loading of the barbell with the same plates on both sides.

The second constraint introduces a variable \(q_i\), which is the number of plates of type \(i\) needed across all work sets. We use \(\max_j x_{ij}\) plates of type \(i\) across all work sets, and the constraint \(q_i \geq x_{ij}\) introduces a variable that’s at least as large as the maximum. We want to minimize \(\sum_i q_i\), which is the number of plates of all types needed across all work sets. Using the constraint \(q_i \geq x_{ij}\) to model \(q_i = \max_j x_{ij}\) is justified because of the minimization of the objective function.

\begin{align} & \text{minimize}   && \sum_i q_i  \\ & \text{subject to} && 2 \sum_i w_{i} x_{ij} + 20 = W_j && \forall \, j  \\ & && q_i \geq x_{ij} && \forall \, i, j \\ & && q_i, x_{ij} \in \mathbb{Z}_+ \end{align}

The optimization model is only a few lines of math – simple and easy!

Plate loading and canonical coin systems

Consider finding the fewest plates needed for a single work set of a desired weight.

This problem is isomorphic to the coin change-making problem, which asks for coin change using the least amount of coins possible. The change-making problem is itself a special case of the more general knapsack problem. The change-making problem is NP-hard in general, but can be solved by a greedy algorithm if and only if the coin system is canonical. The cashier can then give change using a minimal amount of coins by repeatedly using the biggest coin whose value is no larger than the remaining amount.

For instance, a coin system with coins of denominations \(\{ 1, 3, 4 \}\) is not canonical. To see this, notice that a greedy algorithm would given change for \(6\) as \((1) \times 4 + (2) \times 1\) and use \(3\) coins – but clearly \((2) \times 3\) is optimal and only uses \(2\) coins. Most real-world coin systems are canonical.

Loading a barbell to a specified weight can be solved optimally by the greedy algorithm. In other words, the strategy “repeatedly use the heaviest plate whose weight is no larger than the remaining difference” guarantees that a minimal number of plates are used. This is true because the metric plates are, when divided by \(1.25\), isomorphic to the coin system \(\{1, 2, 4, 8, 12, 16, 20\}\), and this coin system is canonical.

One important question remains: how can we know if a given coin system is canonical? It turns out that determining whether a coin system is canonical can be done in \(\mathcal{O}(n^3)\) time, where \(n\) is the number of coins. This is amazing, since for a specific value of change under a coin system, it’s NP-hard to determine whether the greedy algorithm is optimal. Yet for all values of change under a specific coin system, it’s polynomially decidable to determine whether the greedy algorithm is optimal.

Occasionally we get lucky and encounter structures in which greedy algorithms turn out to be optimal. This is the case for weightlifters loading barbells for a single set. No such luck is present when planning across several sets. But then again, who needs luck when armed with a state-of-the-art Integer Program solver?

An algorithm for greedy coin change

The \(\mathcal{O}(n^3)\) algorithm is given in the paper “A Polynomial-time Algorithm for the Change-Making Problem” by D. Pearson, published in 2005. I was unable to find an implementation online, so I include my own Python 3.7 implementation below. A more polished version of this code may be found here: canonical_coin_systems.py

def greedy_coin_change(change: int, coins: list) -> list:
    """Attempt to represent `change` using `coins` by repeatedly taking the 
    biggest coin whose value is no larger than the remaining amount.

    >>> greedy_coin_change(6, coins=[4, 3, 1])
    [1, 0, 2]
    >>> greedy_coin_change(6, coins=[4, 2, 1])
    [1, 1, 0]

    assert sorted(coins, reverse=True) == coins

    representation = [0 for _ in coins]  # Create an empty solution list
    for i, coin in enumerate(coins):
        # If the coin can be subtracted from the change
        if coin <= change:
            multiplier = change // coin  # How many times can we subtract?
            representation[i] = multiplier  # Add to the solution
            change -= multiplier * coin  # Subtract the coin(s)

    # The algorithm can fail, for instance on change=12 and coins=[8, 3]
    if change > 0:
        raise Exception("Greedy algorithm did not terminate.")
    return representation

def is_canonical(coins: list) -> bool:
    """Is the coin system given by `coins` canonical?

    >>> is_canonical(coins=[4, 3, 1]) # Not canonical, since 6 = 3 + 3 
    >>> is_canonical(coins=[25, 10, 5, 1]) # Norwegian coins
    assert sorted(coins, reverse=True) == coins

    # Loop over every possible combination of indices
    for i in range(1, len(coins)):
        for j in range(i, len(coins)):

            # Compute the representation of G(c_{i-1} - 1)
            G_c = greedy_coin_change(change=coins[i - 1] - 1, coins=coins)

            # From the representation of G(c_{i-1} - 1), Theorem 1 in the paper
            # gives us a way to compute M(w), where w is the minimal candidate
            M_w = G_c.copy()  # M(w) is equal for indices 1 through j - 1
            M_w[j] = M_w[j] + 1  # M(w) is one greater in entry j
            M_w[j + 1:] = [0] * (len(M_w) - (j + 1))  # Remaining indices = 0

            # From M(w) we can compute the candidate minimal counterexample w
            w = sum(c_i * r_i for (c_i, r_i) in zip(coins, M_w))
            # The greedy representation of w
            G_w = greedy_coin_change(change=w, coins=coins)
            if sum(M_w) < sum(G_w):
                return False

    return True