Constructive Neural Policies for the Quadratic Assignment Problem via Multi-Expert Imitation

The quadratic assignment problem (QAP) is widely considered one of the most difficult NP-hard combinatorial optimization problems, and one that remains challenging for neural constructive methods. We introduce CIMP, a Constructive policy trained by Imitation from Multi-expert teachers and built around an explicit Pairwise pre-conditioning block. CIMP reaches a 11.02% mean optimality gap on the 133 QAPLIB instances with published reference values, across 5 fixed same-config seeds, in a single constructive pass — without local search or per-instance refinement — with inference times between 0.1 and 3.1 seconds per instance. The model is trained on 400 synthetic instances with n ≤ 25. The most recent published neural reference reporting full QAPLIB results is SAWT [Tan and Mu, ICML 2024], a learn-to-improve (L2I) method that iteratively refines an assignment per instance after training on 5,120 synthetic instances, and reports a 26.8% mean gap. CIMP operates in a strictly more constrained learn-to-construct (L2C) regime and from a much smaller training budget, yet attains a substantially lower mean gap. The pre-block builds a state-dependent facility–location representation before scoring, a hybrid context-biased decoder mixes learned content similarity with QAP-specific algorithmic bias terms, and a sequence-distribution distillation objective is derived from a diversity-filtered pool of heuristic teachers. Family-wise and size-conditioned analyses, supported by a secondary normalized score, indicate that the gain is broadly consistent across QAPLIB families and across instance sizes beyond the training range.