How 0‑1 Integer Programming Solves Assignment Problems: A Relay Team Example

0‑1 Planning

When the integer decision variables in an integer programming problem are restricted to 0 or 1, the problem is called 0‑1 integer programming, or 0‑1 planning.

Because the solution space of 0‑1 problems is smaller than that of general integer programs, they are easier to solve, and any integer program can be transformed into a 0‑1 program; therefore, when building mixed‑integer models, 0‑1 variables should be used whenever possible.

Example: If ten factories are under consideration, ten 0‑1 variables can indicate whether each factory is used (1) or not (0).

Common solution methods for 0‑1 planning include branch‑and‑bound, cutting‑plane, and implicit enumeration.

Assignment Problem

The assignment problem seeks to allocate each person to exactly one task so that the total cost (or time) is minimized.

Solution: Introduce binary variables x_{ij} that equal 1 if person i is assigned to task j, otherwise 0. The mathematical model includes constraints ensuring each person is assigned to one task and each task receives exactly one person.

Case Study: Relay Team Division

Four relay swimmers A, B, C, D have the following best times (lower is better) for four strokes.

Stroke1 Stroke2 Stroke3 Stroke4
A       56      74      61      63
B       63      69      65      71
C       57      77      63      67
D       55      76      62      62

Solution: Formulate the problem as an assignment model with binary variables indicating which swimmer performs which stroke, then solve using Python’s PuLP library.

Optimal assignment:
A -> Stroke3
B -> Stroke2
C -> Stroke1
D -> Stroke4
Total time = 249.0