Branch and Bound Meets Genetic Algorithms for the Quadratic Assignment Problem: A Recent Matheuristic Perspective

The Quadratic Assignment Problem (QAP) assigns nfacilities to nlocations to minimize pairwise flow distance costs and remains among the most challenging NP-hard combinatorial problems. Exact Branch-and-Bound (B B (ii) pure GA leaves 1–3% gaps at n≈20; (iii) the hybrid closes gaps to ≤0.5% or improves GA best by ≈ 3–6% by the 30-minute budget at n≈30. The design aligns with recent evidence on hybrid GA/tabu schemes and tightened bounds for QAP. We analyze ablations (crossover, local search depth, adaptive mutation), report sensitivity to instance features, discuss practical implications for layout planning, and outline extensions in robust QAP and parallelization.