Solving the Assignment Problem with Python
Imagine you’re a project manager with a pool of engineers and a set of tasks. Each engineer has different skill ratings for each task. Your goal? Assign engineers to tasks so that the total performance score is maximized — with each engineer assigned to exactly one task and each task handled by exactly one person.
This is the classic Team Formation / Assignment Problem, and it’s a perfect playground for combinatorial optimization.
🧩 Problem Setup
We have 5 engineers and 5 tasks:
| Task A (Frontend) | Task B (Backend) | Task C (ML) | Task D (DevOps) | Task E (Security) | |
|---|---|---|---|---|---|
| Alice | 90 | 75 | 60 | 55 | 70 |
| Bob | 65 | 85 | 80 | 70 | 60 |
| Carol | 70 | 60 | 95 | 65 | 75 |
| Dave | 80 | 70 | 65 | 90 | 85 |
| Eve | 60 | 80 | 75 | 85 | 95 |
Objective: Maximize total skill score subject to:
$$\sum_{j} x_{ij} = 1 \quad \forall i \quad \text{(each engineer gets one task)}$$
$$\sum_{i} x_{ij} = 1 \quad \forall j \quad \text{(each task gets one engineer)}$$
$$x_{ij} \in {0, 1}$$
The total score to maximize:
$$Z = \sum_{i}\sum_{j} c_{ij} \cdot x_{ij}$$
🐍 Python Solution
We solve this using three approaches:
- Brute-force (for reference)
- Hungarian Algorithm via
scipy.optimize.linear_sum_assignment - PuLP integer linear programming
1 | # ============================================================ |
📖 Code Walkthrough
1. Problem Definition
The score_matrix is a 5×5 NumPy array where score_matrix[i][j] is the skill score of engineer i doing task j. Higher is better.
2. Brute-Force
We enumerate all $n! = 5! = 120$ permutations. For each permutation perm, row $i$ is assigned column perm[i]. This guarantees the global optimum but explodes at $O(n!)$ — utterly impractical beyond $n \approx 12$.
3. Hungarian Algorithm (via scipy)
linear_sum_assignment implements the Hungarian algorithm in $O(n^3)$. Since it minimizes, we negate the matrix to convert our maximization problem. This is the production-grade approach for medium-to-large instances.
4. Integer Linear Programming (PuLP)
We define binary variables $x_{ij} \in {0,1}$ and pass the problem to the CBC solver. ILP is more flexible — it can handle side constraints (e.g., “Alice cannot do Security”) simply by adding extra constraint rows, which neither brute-force nor Hungarian supports easily.
5. Scalability Benchmark
We generate random matrices of increasing size and time both brute-force and Hungarian. Brute-force is skipped for $n=10$ to avoid timeout. The log-scale plot in the chart makes the $O(n!)$ vs $O(n^3)$ gap dramatic and clear.
📊 Graph Explanations
Plot 1 – Skill Score Matrix Heatmap: Yellow-to-red gradient shows raw skill levels. Bright red cells are top performers for that task.
Plot 2 – Optimal Assignment: The same heatmap, but optimal cells are circled in red. You can instantly see that the algorithm avoids obvious-looking choices (e.g., Carol’s 95 in ML dominates, pulling others into their secondary strengths).
Plot 3 – Assigned Scores Bar Chart: Each bar is one engineer in their assigned role. The red dashed line shows the mean. We want all bars as tall as possible — the optimizer does exactly that.
Plot 4 – Algorithm Runtime: At $n=5$, brute-force is already measurably slower than Hungarian, even though all times are sub-millisecond. ILP carries PuLP’s solver-startup overhead.
Plot 5 – Scalability (log scale): The exponential growth of brute-force vs. the nearly flat Hungarian line tells the whole story. By $n=9$, brute-force is already orders of magnitude slower.
Plot 6 – Radar Chart: Each engineer’s full skill profile overlaid. This shows why the optimizer sometimes picks a “non-obvious” assignment — it balances the entire team, not just individual peaks.
Plot 7 – 3D Full Matrix: All 25 bars colored by the plasma colormap. Tall warm-colored bars are elite matches; short cool-colored bars are mismatches. The 3D view lets you scan both engineer and task axes simultaneously.
Plot 8 – 3D Optimal Assignment: Only the 5 selected assignments are red; everything else fades to grey. The optimal bars are not always the tallest in their column — the algorithm trades local optima for a globally maximized sum.
Plot 9 – Score Distribution: All 120 possible total scores histogrammed. The red line marks the optimal score — it sits at the extreme right tail, confirming we’ve found the true global maximum.
🏆 Results
================================================== Brute-Force Result ================================================== Alice -> Frontend (score: 90) Bob -> Backend (score: 85) Carol -> ML (score: 95) Dave -> DevOps (score: 90) Eve -> Security (score: 95) Total Score : 455 Time : 0.709 ms ================================================== Hungarian Algorithm Result ================================================== Alice -> Frontend (score: 90) Bob -> Backend (score: 85) Carol -> ML (score: 95) Dave -> DevOps (score: 90) Eve -> Security (score: 95) Total Score : 455 Time : 0.1719 ms ================================================== ILP (PuLP / CBC) Result ================================================== Alice -> Frontend (score: 90) Bob -> Backend (score: 85) Carol -> ML (score: 95) Dave -> DevOps (score: 90) Eve -> Security (score: 95) Total Score : 455 Time : 103.575 ms ================================================== Scalability: Brute-Force vs Hungarian ==================================================
[Figure saved as team_formation.png] All done! ✓
Key Takeaways
The assignment problem is a fundamental building block in scheduling, logistics, HR allocation, and competitive team drafting. The Hungarian algorithm gives you an exact optimal solution in polynomial time — there’s rarely a reason to use brute-force beyond $n \approx 8$. When you need additional business constraints (role restrictions, budget caps, skill prerequisites), ILP with PuLP is the natural upgrade path.