A Surrogate-Assisted Genetic Algorithm for the Capacitated Facility Location Problem: Extending Linear Programming–Genetic Algorithm Hybridisation with a Machine Learning Fitness Surrogate

Abstract

The Capacitated Facility Location Problem (CFLP) couples a binary decision of which facilities to open with a continuous transportation-allocation sub-problem. A well-established strategy, previously demonstrated by Ozsoydan and Golcuk (2023), decomposes CFLP into a binary sub-problem solved by an evolutionary/swarm-based search and a continuous transportation sub-problem solved exactly by a linear programming (LP) solver. This paper studies a further hybridisation of the same decomposition: replacing the exact LP fitness evaluation inside the evolutionary loop with a trained machine learning (ML) surrogate model, invoking the exact solver only when a surrogate prediction indicates a new best-known solution. We describe a bootstrap mechanism that trains the surrogate directly from a genetic algorithm's (GA) own search trajectory, removing the need for a pre-existing training corpus, and a confidence-aware evaluation policy governing when exact re-verification is triggered. The proposed Hybrid ML-GA framework and a classical GA baseline are benchmarked on all 40 standard Beasley OR-Library CFLP instances (cap41-cap134, capa-capc). The surrogate-assisted approach recovers the published optimum in its best run on every instance up to 25 facilities, but Wilcoxon signed-rank tests on 400 matched paired runs show the classical GA to be significantly better in every instance-size group - a difference that is practically negligible on the small and medium instances (mean gaps of 0.055% versus 0.125%) yet large on the three 100-facility instances (10.4% versus 19.6%). Three further experiments sharpen the picture. First, an active-learning extension that grows the training corpus roughly tenfold and improves surrogate R^2 on all three large instances nonetheless worsens the optimality gap on two of them, contradicting the intuitive hypothesis that the large-instance deficit is simply a sampling-budget problem. Second, a comparison of four surrogate architectures shows that R^2 is a misleading accuracy metric in this setting - a Random Forest attains R^2 = 0.998 while its MAPE on the same predictions exceeds 500,000%, because Big-M capacity penalties dominate the variance that R^2 normalises against. Third, and most consequentially, substituting the markedly more accurate Gradient Boosting surrogate (bounded worst-case MAPE of 5.5% against the Random Forest's 948,600%) under an otherwise identical protocol changes solution quality negligibly and insignificantly (p = 0.33), producing bit-identical results on 33 of the 40 instances. Together these two negative results expose a structural property of the confidence-aware policy: because the incumbent is updated only after exact verification, the surrogate can discard good candidates but never contribute a solution, so its accuracy is decoupled from the quality of what the search returns. Robustness of individual-based model management above an accuracy threshold is known in the surrogate-assisted evolutionary algorithm literature; what these results add is that mandatory verification makes the decoupling exact rather than statistical, and makes it hold even for a surrogate far below any such threshold. The surrogate's contribution is thus computational rather than qualitative, which explains why improving it does not help and indicates what a solution-quality-improving design would have to change. Full per-run statistics are reported for every instance rather than only best-run gaps, and two implementation defects found during verification - a data-corruption bug in the OR-Library template parser and a thread-safety crash in the classical GA's large-instance fitness evaluator - are documented alongside the results they affected.