← ProjectsOptimization / Allocation problems2025Deployed

School Psychologist Allocation

Splitting the 244 schools of the province of Cosenza among school psychologists: a recursive K-means shrinks the problem from 244 schools to 68 groups, a MILP solved with SCIP assigns the groups under a capacity limit, and 66 staffing scenarios are precomputed so the map can be explored instantly.

Pythonscikit-learnSCIPPySCIPOptLeafletReact
244 → 68
Schools reduced to groups
66
Precomputed scenarios
8.9 km
Average trip, 15 × 1,300
01

Introduction

SummaryTwo minutes

How many school psychologists does a province need, and which schools should each one follow? This project answers both for the province of Cosenza, Italy: 244 schools, 17,709 students, and a staff that is always smaller than anyone would like.

The method has two halves. A K-means reduction first turns the 244 schools into 68 compact groups, so the problem becomes small enough to solve exactly; then an integer program assigns those groups to psychologists, minimising travel under a capacity limit. Sixty-six combinations of staff size and capacity were solved ahead of time — move the sliders below to compare them.

02

Context

ProblemBefore

A fixed number of psychologists has to cover 17,709 students in 244 schools spread over a mountainous province. Each psychologist can follow only so many students, and every school assigned far from where they are based costs hours on the road.

ApproachAfter

Reduce first, then optimise: K-means folds the 244 schools into 68 nearby groups, psychologists are placed where the students are, and an integer program assigns whole groups to psychologists, minimising travel without exceeding capacity — or, when there are not enough psychologists, spreading the overload as evenly as possible.

03

Data

The datasetProvince of Cosenza

One spreadsheet: a row per school site with its school code, the number of pupils and its coordinates. Sites that share a school code are merged into one school — students summed, position averaged — which is the unit the rest of the pipeline works with.

Rows
349 school sites
Schools
244 after merging sites with the same school code
Students
17,709 in total; the largest school has 652, the smallest 5
Coordinates
Latitude and longitude per site; distances are great-circle (Haversine) kilometres
04

Methodology

Pipeline
Schools & students (Excel)Group by school codeRecursive K-means: 244 schools → 68 groupsWeighted K-means places psychologistsMILP assigns groups (SCIP)Re-centre and re-solve66 scenarios as static JSON

Everything left of the solver is cheap and runs once; the solver runs once per scenario, offline. The browser only ever reads the results.

Step 1 · Reducing the problem: from n schools to k groupsK-means

The K-means at the start of the pipeline is not there to place anybody — its job is to make the problem smaller. Assigning n = 244 schools to psychologists means one yes/no decision per school and psychologist, and the solver's effort grows quickly with that count. Neighbouring schools almost always end up with the same psychologist anyway, so they are decided together: K-means groups the 244 schools into k = 68 groups, and the optimiser assigns groups instead of schools.

Start
K-means with 15 clusters over the school coordinates
Split
Any group with more than 500 students is split in two with K-means, recursively, until it fits or is a single school
Result
244 schools → 68 groups, each with at most 500 students (unless it is one large school)
Effect
With 15 psychologists: 244 × 15 = 3,660 binary variables become 68 × 15 = 1,020 — 72% fewer

The cap of 500 students is half the smallest capacity in the grid, so every psychologist can always take at least two groups and the reduction never makes a scenario impossible by itself. The map's “Step 1” view shows the 68 groups and their centroids — the points the optimiser actually sees.

Step 2 · Placing the psychologistsWeighted K-means

A second K-means, this time with as many clusters as psychologists and weighted by the number of students, gives each psychologist a starting base where the students are rather than where the schools are.

After each solve every psychologist is moved to the student-weighted centre of the schools they were given and the model is solved again — up to two more rounds, stopping early when the assignment no longer changes.

Step 3 · The assignment modelMILP · SCIP

Each group goes to exactly one psychologist, and the students a psychologist follows should stay under the capacity. The capacity is soft: when the staff simply cannot cover everybody, the model is allowed to overload, but at a price high enough that it first keeps the worst overload as small as possible, then overloads as few students as possible, and only then minimises kilometres.

When capacity is short the solve is split in two. The first pass finds the smallest possible overload; the second keeps the total overload at that minimum, lets the worst case move by at most 50 students, and spends its time purely on distance — so the reported optimality gap is a gap in kilometres. Pinning the worst case exactly would squeeze every load into a window a few students wide, a packing problem the solver could not close in minutes.

Assignment model, solved per scenario
x[p,g] ∈ {0,1}     group g is served by psychologist p
o[p]   ≥ 0         students above capacity for p
o_max  ≥ o[p]      the largest overload

Σ_p x[p,g] = 1                          every group gets one psychologist
Σ_g students[g] · x[p,g] ≤ C + o[p]     soft capacity C

minimise  10⁶ · o_max  +  100 · Σ_p o[p]  +  Σ_p Σ_g km(p,g) · x[p,g]
05

Interactive

Province of Cosenza15 psychologists · capacity 1300
Leaflet © OpenStreetMap contributors
Scenario
Average trip8.9 km
Longest trip25.8 km
Total capacity19,500
Students over capacity0
Granularity overload0
SolverProven optimal
Binary variables1,020 (vs 3,660)
Students per psychologistcapacity 1,300
06501,300P1: 1186 students of 1300, 21 schoolsP1P2: 1222 students of 1300, 18 schoolsP2P3: 940 students of 1300, 20 schoolsP3P4: 1114 students of 1300, 19 schoolsP4P5: 1231 students of 1300, 10 schoolsP5P6: 1253 students of 1300, 11 schoolsP6P7: 872 students of 1300, 18 schoolsP7P8: 1295 students of 1300, 18 schoolsP8P9: 1054 students of 1300, 22 schoolsP9P10: 1247 students of 1300, 6 schoolsP10P11: 1222 students of 1300, 19 schoolsP11P12: 1297 students of 1300, 7 schoolsP12P13: 1293 students of 1300, 16 schoolsP13P14: 1295 students of 1300, 20 schoolsP14P15: 1188 students of 1300, 19 schoolsP15capacityred = above capacity
All 66 scenarios · average trip (km)click a cell
1,0001,1001,2001,3001,4001,5001011121314151617181920x: psychologists · y: capacity · hatched = overload12.112.112.312.312.112.111.511.211.511.111.311.210.610.710.810.810.911.59.79.49.99.89.610.09.89.010.110.79.09.09.79.913.28.98.88.99.59.28.88.77.87.410.69.78.28.47.97.712.28.58.77.86.66.79.07.56.86.76.56.18.87.78.07.06.16.3
06

Results

ResultsAcross the 66 scenarios
244 → 68
Schools reduced to groups
0
Precomputed scenarios
8.9 km
Average trip, 15 × 1,300
  • The reduction cuts the decision variables by 72%: 3,660 binaries for 15 psychologists at school level become 1,020 at group level.
  • With enough capacity the average school sits 6.1–13.2 km from its psychologist; at a capacity of 1,500, going from 12 to 20 psychologists cuts the average trip from 11.5 km to 6.3 km.
  • When the staff cannot cover every student, no school is left unserved: every psychologist is first filled to capacity, and the excess is shared so the busiest one carries at most 50 students more than the smallest possible peak.
  • 62 of the 66 scenarios are proven optimal and the other four stop within 7.6% of the bound; the whole grid solves offline in about five minutes and ships to the browser as 27 KB of compressed JSON.
07

Technical explanation

Why precomputeRaspberry Pi

This site is served from a Raspberry Pi in a home lab. A single solve takes from seconds to a few minutes of full CPU on a desktop — run on demand, a handful of visitors moving a slider would saturate the Pi. Solving the whole grid once, offline, turns the interactive part into a lookup.

Grid
10–20 psychologists × capacity 1,000–1,500 in steps of 100
Solver
SCIP 10 through PySCIPOpt, 60 s per solve, one thread per scenario, 19 scenarios in parallel
Output
One JSON per scenario plus a shared list of schools and groups
The price of the reductionGranularity

Groups cannot be split, so the optimiser packs blocks of up to 500 students instead of single schools. When the total capacity is only just enough, those blocks may not fit exactly, and a little overload appears even though, on paper, there is room for everybody. The explorer reports it separately as “granularity overload”.

Travel is always measured school by school, from each school to its psychologist, not from the group centre — so the kilometres shown are the real cost of the grouped solution, not of the simplified one.

08

Conclusion

What held upRetrospective
  • Reducing before optimising keeps the model small enough to solve exactly: 62 of 66 scenarios are proven optimal and the whole grid takes about five minutes.
  • Soft capacity with a lexicographic objective turns “infeasible” into a useful answer — how many students are left over and how evenly the extra load can be shared.
  • Distances are straight lines; in a mountainous province road time would be the better cost, and is the obvious next step.
  • Staff placement is still a heuristic — K-means plus re-centring — so a few neighbouring scenarios are not monotonic: the assignment is optimal for the bases chosen, not the bases themselves.
  • The group cap is a dial between model size and precision: at 500 students per group, granularity overload appears in only 2 of the 66 scenarios.
© 2026 Héctor LiceaDesign concept · placeholder contentBuild 2026.08Rendered client-side · no tracking