Inspector Assignment Walkthrough

ILP, LP relaxation, sensitivity testing, and stakeholder visualizations — the full uber-polya pipeline on a real assignment problem.

This walkthrough traces every step of the uber-polya trilogy (/uber-model, /uber-solve, /uber-interpret) on the Food Safety Inspector Assignment problem. You will see how a plain-English problem becomes a formal ILP, gets solved to proven optimality, and is translated into actionable recommendations with charts.

Runnable code: examples/inspector-assignment/

The Problem

A food safety agency needs to assign 6 inspectors to 10 facilities (5 types, 2 each) to maximize total expertise. Each inspector handles at most 3 facilities. Each facility needs exactly 1 inspector.

Expertise Matrix

Each inspector has a skill score (1–9) for each facility type.

Inspector	Dairy	Meat	Bakery	Seafood	Beverage
Alice	9	7	4	3	6
Bob	5	9	6	8	3
Carol	7	4	9	5	8
Dave	3	6	5	9	4
Eve	6	3	7	4	9
Frank	8	5	3	6	7

Notice the diagonal. Five inspectors each have a clear specialty (score 9). Frank has no 9 — his best is Dairy (8), which is Alice's domain. This hint foreshadows the optimal solution.

PHASE 1 /uber-model

Problem Understanding

uber-model begins by classifying the problem type and extracting the four Polya elements.

Element	Value
Problem Type	Find (optimization)
Unknown	Assignment that maximizes total expertise
Data	6 inspectors, 10 facilities (5 types × 2), expertise matrix
Conditions	Capacity ≤ 3 per inspector, coverage = 1 per facility

Structure Recognition

The problem maps to a well-known structure in combinatorial optimization.

Capacitated Weighted b-Matching on a bipartite graph.

Inspector → left vertex. Facility → right vertex. Expertise → edge weight.

The bipartite structure means we have two disjoint sets (inspectors and facilities) with edges only between them — never within the same set.

Real World	Math
Inspector	Left vertex in bipartite graph
Facility	Right vertex in bipartite graph
Expertise score	Edge weight w(i, f)
"at most 3 facilities"	Degree ≤ 3 (capacity constraint)
"exactly 1 inspector"	Degree = 1 (coverage constraint)
Maximize total expertise	Maximize ∑ w(i,f) · x(i,f)

Formal Model

The formal model uses binary decision variables x_i,f ∈ {0, 1} indicating whether inspector i is assigned to facility f.

ILP Formulation

maximize ∑_{i ∈ I} ∑_{f ∈ F} w(i,f) · x_i,f

subject to:

∑_{f ∈ F} x_i,f ≤ 3 ∀ i ∈ I (capacity)

∑_{i ∈ I} x_i,f = 1 ∀ f ∈ F (coverage)

x_i,f ∈ {0, 1} ∀ i, f (integrality)

Key observation: total unimodularity. The constraint matrix is totally unimodular (TU) — a consequence of the bipartite structure with ≤ and = constraints. This means the LP relaxation (replacing x ∈ {0,1} with 0 ≤ x ≤ 1) always produces an integer optimum. We get ILP-quality solutions at LP speed.

PHASE 2 /uber-solve

Problem Classification

Binary Vars

Constraints

Matrix

Poly

Complexity

Property	Value
Named Problem	Capacitated Weighted Bipartite b-Matching
Complexity	Effectively polynomial (TU constraint matrix)
Variables	60 binary (6 inspectors × 10 facilities)
Constraints	16 (10 coverage + 6 capacity)
Algorithm	ILP via PuLP/CBC (Branch & Bound)
Verification	LP relaxation bound + independent constraint checking

The ILP Formulation

The complete solver code using PuLP. This is the core of inspector_solver.py.

inspector_solver.py (core)

from pulp import LpProblem, LpVariable, LpMaximize, LpBinary, lpSum, PULP_CBC_CMD, value

# Binary decision variables: x[i,f] = 1 if inspector i assigned to facility f

prob = LpProblem("inspector_assignment", LpMaximize)

x = {(i, f): LpVariable(f"x_{i}_{f}", cat=LpBinary)

for i in inspectors for f in facilities}

# Objective: maximize total expertise

prob += lpSum(score(i, f) * x[i, f]

for i in inspectors for f in facilities)

# Constraint 1: capacity ≤ 3 per inspector

for i in inspectors:

prob += lpSum(x[i, f] for f in facilities) <= 3

# Constraint 2: exactly 1 inspector per facility

for f in facilities:

prob += lpSum(x[i, f] for i in inspectors) == 1

# Solve

prob.solve(PULP_CBC_CMD(msg=False))

Solution

Objective

90.0

LP Relaxation

Gap

100%

Efficiency

The solver finds a perfect assignment — every facility is covered by its top expert.

Inspector	Assigned To	Score
Alice	Dairy (F1, F2)	18 (9+9)
Bob	Meat (F3, F4)	18 (9+9)
Carol	Bakery (F5, F6)	18 (9+9)
Dave	Seafood (F7, F8)	18 (9+9)
Eve	Beverage (F9, F10)	18 (9+9)
Frank	Reserve (none)	0

Objective: 90 out of 90 possible points. The LP relaxation confirms optimality with gap = 0. Each of the five specialists is assigned to their strongest type. Frank, with no unique top skill, is left as a reserve — which turns out to be strategically valuable.

Independent Verification

The verify() function checks all constraints independently of the solver — no shared logic.

verification output

PASS capacity_Alice ........ 2 ≤ 3

PASS capacity_Bob .......... 2 ≤ 3

PASS capacity_Carol ........ 2 ≤ 3

PASS capacity_Dave ......... 2 ≤ 3

PASS capacity_Eve .......... 2 ≤ 3

PASS capacity_Frank ........ 0 ≤ 3

PASS coverage_F1..F10 ...... all = 1

PASS all_facilities_covered 10/10

PASS objective_recomputed .. 90 = 90

Sensitivity: What If an Inspector Leaves?

For each inspector, we remove them and re-solve to measure the impact on total expertise.

Inspector Removed	New Objective	Delta	Risk Level
Alice	88	-2	LOW
Bob	85	-5	MODERATE
Carol	85	-5	MODERATE
Dave	86	-4	LOW
Eve	87	-3	LOW
Frank	90	0	NONE

PHASE 3 /uber-interpret

Bottom Line

A perfect assignment exists. Every facility gets its top-scoring inspector. Total expertise: 90/90 (100% efficiency). Frank serves as a reserve inspector, available for emergencies or substitution without disrupting any assignment.

100%

Efficiency

Active Inspectors

Reserve

Optimality Gap

Stakeholder Visualizations

Three charts generated by inspector_viz.py, each targeting a different stakeholder question.

Chart 1: Expertise Heatmap

Audience: Operations manager. Question: "Who is assigned where and why?"

A 6×10 matrix with expertise scores color-coded from low (yellow) to high (red). Optimal assignments are outlined with thick blue borders. Reveals the block-diagonal structure: each specialist covers their top-scoring type pair.

viz_assignment_matrix.png

Chart 2: Sensitivity Tornado

Audience: Risk manager. Question: "What happens if someone leaves?"

Horizontal bar chart showing the objective drop per inspector removal. Bob and Carol cause the largest impact (-5 points each). Frank's removal has zero impact. Color-coded: red = moderate risk, yellow = low risk, green = no impact.

viz_sensitivity_tornado.png

Chart 3: Workload Distribution

Audience: HR / scheduling team. Question: "Is the workload fair?"

Side-by-side bar charts: facilities assigned (left) and expertise score contribution (right). All active inspectors carry exactly 2 facilities out of a maximum 3, contributing 18 points each. Frank carries 0. Capacity slack: 1 facility per inspector.

viz_workload_expertise.png

Sensitivity Deep Dive

Block-Diagonal Structure

The optimal assignment has a clean block-diagonal structure: each inspector is paired with exactly one facility type. This makes the solution easy to understand, implement, and maintain. It also means disruptions are localized — losing one inspector only affects their type pair.

Critical Personnel

Bob (Meat) and Carol (Bakery) are the most critical inspectors. Losing either drops the objective by 5 points (-5.6%). Their skills are the hardest to replace because no other inspector scores above 6 in their specialty.

Recommendation: Cross-train Bob and Carol. Their departure risk is the highest. Cross-training a second inspector in Meat and Bakery reduces the maximum single-point-of-failure from -5 to approximately -2.

Frank as Insurance

Frank is not idle — he is insurance. His broad skill profile (8, 5, 3, 6, 7) means he can step in for any inspector with a score of at least 5 in most types. Removing Frank from the team has zero impact on the current optimal, but his presence is what makes the system resilient.

Capacity Slack

Every active inspector uses 2 out of 3 capacity slots. The remaining slack of 1 per inspector (plus Frank's full 3-slot capacity) provides headroom for future facility additions without restructuring.

Recommendations

Primary

Implement the optimal assignment as computed
Each specialist covers their top-scoring type pair
Frank held in reserve for substitution

Monitor

Bob and Carol: initiate cross-training program
Track expertise scores quarterly (static scores may drift)
Re-run solver if staffing or facility count changes

Risk Mitigation

Keep Frank as dedicated reserve inspector
Document substitution protocol for each type pair
Alert threshold: re-solve if any inspector's score drops below 7

Limitations

Static expertise scores (no learning curve)
No travel time between facilities
Equal weighting across facility types
No inspector preferences considered

Knowledge Transfer

Pattern: "Assign people to roles by skill with capacity limits" → weighted bipartite b-matching via ILP.

This is one of the most common optimization patterns in practice. Whenever you see people, skills, capacity, and a score to maximize, reach for this formulation.

Same Pattern, Different Domain

Application	Left Vertices	Right Vertices	Edge Weight
Student-Project	Students	Projects	Preference score
Nurse-Shift	Nurses	Shifts	Competency score
Truck-Route	Trucks	Routes	Efficiency score
Reviewer-Paper	Reviewers	Papers	Expertise score

In every case: formulate as ILP with binary variables, check for TU structure, solve with PuLP, verify independently. The entire pipeline transfers directly.

Running the Code

terminal

# Navigate to the example directory

$ cd examples/inspector-assignment/

# Install dependencies

$ pip install pulp

# Run the solver

$ python inspector_solver.py

==================================================

SOLUTION REPORT: Food Safety Inspector Assignment

==================================================

[RESULT] Status: Optimal

[RESULT] Objective: 90 (total expertise score)

[RESULT] LP Bound: 90.0

[RESULT] Gap: 0.0 (0.0%)

[RESULT] Efficiency: 100.0%

[VERIFY] PASS capacity checks (6/6)

[VERIFY] PASS coverage checks (10/10)

[VERIFY] PASS objective recomputed: 90

[SAVE] solution.json

terminal

# Generate stakeholder visualizations

$ pip install matplotlib numpy

$ python inspector_viz.py

[SAVE] viz_assignment_matrix.png

[SAVE] viz_sensitivity_tornado.png

[SAVE] viz_workload_expertise.png

[COMPLETE] All 3 visualizations generated successfully.

What You Learned

Concept	What You Saw
Modeling	Real-world assignment → capacitated weighted bipartite b-matching via ILP
Algorithm	ILP solved by PuLP/CBC with Branch & Bound
Total Unimodularity	Bipartite structure guarantees LP relaxation = ILP optimum
Verification	Independent `verify()` checks all constraints and recomputes objective
Sensitivity	What-if analysis: remove each inspector, measure objective drop
Interpretation	Block-diagonal structure, critical personnel, reserve value, capacity slack
Knowledge Transfer	Pattern: "assign by skill with capacity" → ILP. Applies to nurses, students, trucks, reviewers.

← Previous Milking Cows Walkthrough