acceptodds
Under review as a conference paper at ICLR 2027

QAP-SCP: Learning Structural Compatibility Priors for Quadratic Assignment

Abstract

The quadratic assignment problem (QAP) remains challenging under limited search budgets because solution quality depends strongly on which search basins are reached. Rather than replacing combinatorial search, we propose QAP-SCP, a learning framework that predicts where search should begin. Given a QAP instance, QAP-SCP constructs a compatibility-aware structural representation that captures interaction profiles, relative structural roles, and assignment-specific compatibility, and maps them to an additive assignment score matrix. The scorer is trained with staged search-aware supervision: exact local refinement provides both a refined assignment target and exchange-geometry signals, while a compatibility module is introduced as a zero-initialized correction to a learned structural prior. At inference, deterministic and perturbed decoding convert the learned score matrix into a diverse multi-start proposal portfolio, which is filtered using the exact QAP objective and passed to a replaceable search backend. This design preserves exact objective evaluation and backend search dynamics while using learning only to guide initialization. Experiments on QAPLIB, Taixxeyy, and synthetic QAP distributions show that QAP-SCP achieves competitive standalone construction quality and substantially reduces long-tail failures on basin-sensitive instances, while maintaining low final gaps on standard QAP benchmarks. Ablations further show the contributions of compatibility-aware representations, exchange-geometry supervision, and learned proposal diversification.

Primary area:
optimization
Keywords:
Quadratic Assignment Problem, Structural Compatibility, Search-aware Learning

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_b9BnOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes QAP-SCP, a learned proposal mechanism for the quadratic assignment problem. Instead of replacing combinatorial search, it predicts a score matrix over facility-location pairs using structural descriptors, FAQ/spectral compatibility features, and a staged training procedure based on locally refined assignments and exact swap costs. Hungarian decoding and Gumbel perturbations produce a multi-start proposal set, which is filtered by the exact QAP objective and passed to a BLS backend. Experiments on synthetic instances, Taixxeyy, and QAPLIB show large reductions in long-tail failures on Taixxeyy, while gains on QAPLIB and synthetic data are relatively small and not consistently significant.

Critical strengths
  1. The paper makes a sensible design choice by using learning to generate search proposals while retaining exact objective evaluation and established local-search dynamics.
  2. The evaluation is relatively careful for a heuristic method.
Critical weaknesses
  1. The main empirical gain is not cleanly attributable to QAP-SCP. On Taixxeyy, most of the improvement comes from replacing a single BLS start with a large proposal portfolio and short probes; the learned-versus-random source improvement is much smaller.
  2. The “backend-agnostic” claim is not sufficiently validated. All main end-to-end experiments use BLS, it remains unclear whether the learned proposals transfer to other search dynamics or whether the method is specifically tuned to BLS and its probe/allocation scheme.
Questions for authors
  1. What instances, sizes, and distributions are used to train the model and select Stage-1/Stage-2 checkpoints?
  2. Can the authors provide an end-to-end comparison using a second search backend, with the same candidate counts, probe allocation, and wall-clock budget?
Reviewer_HfSAOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This paper proposes QAP-SCP, a learning-based predict-and-optimize framework for the quadratic assignment problem. It combines structural and assignment compatibility features to generate candidate solutions, using local-search supervision for training. These candidates are combined with random starts and refined by a conventional search solver. Experiments on synthetic instances, QAPLIB, and Taixxeyy show the largest gains on Taixxeyy, with smaller improvements on the other benchmarks.

Critical strengths
  1. The results on Taixxeyy demonstrate a meaningful benefit from learned prediction. Under the same BLS backend and time budgets, QAP-SCP reduces the mean gap from 22.10% with random multi-start to 14.20%. This comparison supports the value of the learned proposals beyond the gains from multi-start search alone.
Critical weaknesses
  1. The methodological contribution is not sufficiently established. The architecture and staged training are reasonable engineering choices, but their substantive advantages over PLMA and simpler alternatives remain unclear. Missing comparisons against FAQ-generated initializations and joint training make it difficult to determine whether the proposed learning components are necessary. This weakens the evidence for the paper’s novelty.

  2. The experimental evidence does not yet establish a reliable advantage over PLMA. Important training, inference details and abations are missing, and the relationship between the PLMA variants used in the experiments and the original solver requires clarification. Moreover, performance gains are inconsistent across settings, with no direct paired confidence intervals or adequate multi-seed evaluation against full PLMA. These gaps limit confidence in the fairness, reproducibility, and stability of the reported improvements.

Questions for authors
  1. What is the key methodological contribution of QAP-SCP beyond PLMA and other methods, apart from differences in features, network architecture and search strategy?
  2. How much of the downstream improvement comes from learning beyond the FAQ-derived compatibility signal? The authors sholud compare QAP-SCP with FAQ-based proposals using the same candidate count, BLS allocation scheme, and total time budget.
  3. How sensitive are the reported improvements over PLMA to random seed selection? The authors should provide paired comparisons across multiple seeds, with confidence intervals, to establish whether these gains are statistically robust under matched computational budgets.
Reviewer_5G9ROpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper learns initial assignments for QAP and passes them to a conventional search solver. The model uses structural statistics and FAQ-based features to score assignments. It is trained on solutions obtained by local search, with an additional loss based on swap costs. At inference, learned and random proposals are combined, filtered, and refined using BLS.

Critical strengths

Learning initial solutions while keeping an established search solver is a practical design. The paper includes proposal generation and refinement within the reported runtime budgets.

The experiments compare learned proposals with random proposals using the same search backend. On Taixxeyy, the learned portfolio improves over random multi-start search. The paper also reports confidence intervals and acknowledges the limited gains on QAPLIB.

Critical weaknesses
  1. The methodological novelty appears limited. Using local search to generate training labels, learning assignment scores, and using those scores to initialize further search follows a familiar approach. The proposed changes mainly involve structural features, a swap-cost loss, and staged training. The paper does not clearly establish what these changes add beyond existing methods or whether the gains justify the additional training and preprocessing costs.

  2. The gains on the synthetic benchmarks are nearly zero, and the improvement over BLS on QAPLIB is not statistically clear. The paper also does not adequately report label-generation and training costs, making it difficult to judge whether the added complexity is worthwhile.

Questions for authors

What is novel about learning from search-generated labels in this setting? Why choose supervised training over reinforcement learning or unsupervised learning, and what evidence supports this choice?

  1. What is the main contribution beyond existing methods that learn initial solutions from search-generated labels?

  2. How does the method compare with direct FAQ-based proposals under the same search budget?

  3. Given the small gains on synthetic instances and inconclusive improvement on QAPLIB, when is the learned component worth using?

  4. What are the total costs of generating training labels and training the model?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.