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) can certify optimality using strong lower bounds and pruning, yet becomes computationally prohibitive beyond moderate instance sizes. Genetic Algorithms (GA) scale to larger sizes and discover high-quality permutations quickly but cannot guarantee optimality. This paper develops a simple, effective matheuristic handshake: GA supplies tight incumbents (upper bounds, UB) that accelerate B&B pruning; B&B, in turn, refines elite GA permutations and provides structural guidance that directs GA away from weak regions. We formalize the Koopmans Beckmann QAP, detail assignment-based lower bounds and permutation-preserving GA operators, and propose an orchestration scheme with lightweight feedback. Using standard QAPLIB-style instances and a logistics-flavored variant with capacity/demand penalties, synthetic but realistic results show: (i) pure B&B proves optimality rapidly for small nbut explores far more nodes than the hybrid; (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.