Swim relay problem (Van Roy and Mason)

The coach of a swim team needs to assign swimmers to a 200-yard medley relay team to compete in a tournament. The problem is that his best swimmers are good in more than one stroke, so it's not clear which swimmer to assign to which stroke. Here are the best times for each swimmer:

Stroke Carl Chris David Tony Ken
Backstroke 37.7 32.9 33.8 37.0 35.4
Breaststroke 43.4 33.1 42.2 34.7 41.8
Butterfly 33.3 28.5 38.9 30.4 33.6
Freestyle 29.2 26.4 29.6 28.5 31.1

Solution

In [2]:
using JuMP, Clp, NamedArrays

strokes = [ :backstroke, :breaststroke, :butterfly, :freestyle ]
names = [ :Carl, :Chris, :David, :Tony, :Ken ]

raw = [ 37.7 32.9 33.8 37.0 35.4
        43.4 33.1 42.2 34.7 41.8
        33.3 28.5 38.9 30.4 33.6
        29.2 26.4 29.6 28.5 31.1 ]

times = NamedArray( raw, (strokes,names), ("stroke","name"))

m = Model(solver=ClpSolver())

@variable(m, x[strokes,names] >= 0)

# each swimmer swims at most one event
@constraint(m, a[j in names], sum(x[i,j] for i in strokes) <= 1 )

# each event has exactly one swimmer
@constraint(m, b[i in strokes], sum(x[i,j] for j in names) == 1 )

@objective(m, Min, sum( x[i,j]*times[i,j] for i in strokes, j in names ) )

solve(m)

assignment = NamedArray( [ (getvalue(x[i,j])) for i in strokes, j in names ], (strokes, names), ("stroke","name"))
Out[2]:
4×5 Named Array{Float64,2}
stroke ╲ name │  :Carl  :Chris  :David   :Tony    :Ken
──────────────┼───────────────────────────────────────
:backstroke   │    0.0     0.0     1.0     0.0     0.0
:breaststroke │    0.0     0.0     0.0     1.0     0.0
:butterfly    │    0.0     1.0     0.0     0.0     0.0
:freestyle    │    1.0     0.0     0.0     0.0     0.0
In [ ]: