Reproducible implementation and confirmatory results for a Pareto Local-Branching Variable Neighborhood Search applied to a biobjective Generalized Assignment Problem derived from NYC TLC/FHV data.
This repository accompanies the SBPO 2026 extended abstract:
A Pareto Local-Branching VNS for a Real-Data-Derived Biobjective Generalized Assignment Problem with Multicriteria Decision Support
PLB-VNS combines global Pareto exploration with exact neighborhood intensification:
- integer NSGA-II generates an initial nondominated archive;
- 15 strict epsilon targets define imbalance levels;
- HiGHS reoptimizes Hamming neighborhoods with radii 4, 8, and 12;
- feasible nondominated solutions update an external Pareto archive.
The objectives minimize total assignment cost and the range of relative agent utilization. Assignment, capacity, and epsilon constraints are enforced explicitly.
Thirty paired seeds (100–129) were evaluated on the 10-agent, 120-task instance. Seed 42 was used only during development.
| Method | Median HV [IQR] | Median runtime [IQR] | Computational effort |
|---|---|---|---|
| NSGA-II initializer | 0.85619 [0.04343] | 190.32 s [10.13] | 150k evaluations |
| NSGA-II baseline | 0.86349 [0.03739] | 308.73 s [27.76] | 250k evaluations |
| PLB-VNS | 0.90325 [0.03385] | 281.31 s [10.41] | 150k evaluations + 45 MIPs |
PLB-VNS won 28 of 30 paired comparisons against the baseline
(p = 1.86 × 10⁻⁸, rank-biserial effect 0.9785). The claim is restricted to
the reported instance and protocol.
Requirements: Python 3.10+ and the dependencies listed in requirements.txt.
python -m venv .venv
python -m pip install -r requirements.txt
python -m pytest -qRun the complete experiment with checkpoint/resume support:
powershell -ExecutionPolicy Bypass -File scripts/run_experiment.ps1 -Jobs 8JOBS=8 sh scripts/run_experiment.shEach worker uses one HiGHS thread to avoid CPU oversubscription. The discrete optimization stack does not use a CUDA execution path.
data/ Confirmatory 10×120 instance
docs/ Protocol, results, reviewer response, and paper content
figures/ Publication figures and FITradeoff outputs
results/final/ Aggregates, raw runs, traces, and checkpoints
scripts/ Reproduction entry points
src/ PLB-VNS, experiment orchestration, and decision support
tests/ Feasibility, objective, Pareto, NSGA-II, and MIP tests
- Frozen experimental protocol
- Complete result report
- Extended-abstract content
- Reviewer response
- Run manifest
- Per-run metrics
- Statistical tests
FITradeoff is applied to ten diverse representatives of the pooled reference front using a documented synthetic preference profile. No human elicitation is claimed. The selected alternative is robust for 73.68% of sampled admissible weights.
Local branching and VNS are established methods. The contribution evaluated here is their problem-specific biobjective GAP integration with NSGA-II, strict epsilon constraints, assignment-space neighborhoods, and an auditable Pareto archive. No claim of universal algorithmic superiority is made.