- 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
- The paper makes a sensible design choice by using learning to generate search proposals while retaining exact objective evaluation and established local-search dynamics.
- The evaluation is relatively careful for a heuristic method.
Critical weaknesses
- 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.
- 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
- What instances, sizes, and distributions are used to train the model and select Stage-1/Stage-2 checkpoints?
- 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?