HapLotes405: A Deterministic Multi-Start Capacitated Clustering Heuristic with Regret-Based Assignment

HapLotes405 is a deterministic, type-general heuristic for capacitated clustering: it partitions a set of typed points into a fixed number of groups under per-group, per-type cardinality constraints, while minimizing the sum of squared distances from each point to its group centroid (SSE). The method combines farthest-point initialization, regret-based greedy assignment, and Lloyd iteration within a fixed-seed multi-start scheme, so every run is fully reproducible. The distance function and the objective are pluggable, and the implementation is pure Python with zero dependencies. On synthetic instances of 16–48 points grouped into 3–5 clusters, it lowers mean SSE by 46.5%–56.8% (single start) and 55.0%–64.9% (8 starts) relative to random assignment, and outperforms a nearest-center greedy baseline in every instance. This record contains the Python implementation, the benchmark script, and the accompanying paper.