Optimizing Relay Team Selection with PuLP: A Step‑by‑Step Guide

1. Relay Team Selection Case

Table shows the fastest times of five swimmers A‑E in four strokes; we need to select four swimmers, each assigned a distinct stroke.

1.1 Decision Variables

x_{ij}: binary variable indicating whether person i is assigned stroke j (1 if chosen, 0 otherwise).

1.2 Parameters

t_{ij}: time of person i swimming stroke j.

1.3 Objective Function

Minimize total swimming time.

1.4 Constraints

Each person can swim at most one stroke.

Each stroke can be assigned to only one person.

2. Solving with PuLP

2.1 Initialize Model

<code>import pulp as lp
import pandas as pd
model = lp.LpProblem('swim', lp.LpMinimize)</code>

lp.LpProblem creates a model with a name and sense (LpMinimize or LpMaximize).

2.2 Define Decision Variables

<code># Data and parameters
data = {'stroke1': {'A': 56, 'B': 63, 'C': 57, 'D': 55, 'E': 60},
        'stroke2': {'A': 74, 'B': 69, 'C': 77, 'D': 76, 'E': 71},
        'stroke3': {'A': 61, 'B': 65, 'C': 63, 'D': 62, 'E': 62},
        'stroke4': {'A': 63, 'B': 71, 'C': 67, 'D': 62, 'E': 68}}
swim = pd.DataFrame(data)
persons = swim.columns
strokes = swim.index
x = lp.LpVariable.dicts('x_ij', [(i,j) for i in strokes for j in persons], cat='Binary')
</code>

lp.LpVariable.dicts creates a dictionary of binary variables indexed by stroke and person.

2.3 Define Objective Function

<code>objective = lp.lpSum([swim.loc[i,j] * x[i,j] for i in strokes for j in persons])
model += objective, 'Minimize_the_total_time'</code>

2.4 Add Constraints

<code># Each person swims at most one stroke
for j in persons:
    model += lp.lpSum([x[i,j] for i in strokes]) <= 1, f'constraint_{j}'
# Each stroke assigned to exactly one person
for i in strokes:
    model += lp.lpSum([x[i,j] for j in persons]) == 1, f'constraint_{i}'
</code>

2.5 Solve

<code>model.solve()</code>

solve() uses the default CBC solver; other solvers like GLPK, CPLEX, GUROBI can be used if installed.

2.6 Retrieve Results

2.6.1 Print Model

<code>print(model)</code>

The printed model shows the objective function and constraints.

2.6.2 Print Objective Value and Variable Values

<code>print('Objective value:', lp.value(model.objective))
print('Decision variable values:')
for i in strokes:
    for j in persons:
        print((i,j), lp.value(x[i,j]))
</code>

Value 0 indicates the assignment is not selected; 1 indicates the swimmer is assigned to that stroke.

3. Full Code

<code>import pulp as lp
import pandas as pd
model = lp.LpProblem('swim', lp.LpMinimize)

data = {'stroke1': {'A': 56, 'B': 63, 'C': 57, 'D': 55, 'E': 60},
        'stroke2': {'A': 74, 'B': 69, 'C': 77, 'D': 76, 'E': 71},
        'stroke3': {'A': 61, 'B': 65, 'C': 63, 'D': 62, 'E': 62},
        'stroke4': {'A': 63, 'B': 71, 'C': 67, 'D': 62, 'E': 68}}
swim = pd.DataFrame(data)
persons = swim.columns
strokes = swim.index
x = lp.LpVariable.dicts('x_ij', [(i,j) for i in strokes for j in persons], cat='Binary')
objective = lp.lpSum([swim.loc[i,j] * x[i,j] for i in strokes for j in persons])
model += objective, 'Minimize_the_total_time'
for j in persons:
    model += lp.lpSum([x[i,j] for i in strokes]) <= 1, f'constraint_{j}'
for i in strokes:
    model += lp.lpSum([x[i,j] for j in persons]) == 1, f'constraint_{i}'
model.solve()
print('Objective value:', lp.value(model.objective))
print('Decision variable values:')
for i in strokes:
    for j in persons:
        print((i,j), lp.value(x[i,j]))
</code>