웜 스타팅 MCMC 미세 조정을 이용한 이차 할당 문제 해결 방법

Learning to Solve the Quadratic Assignment Problem with Warm-Started MCMC Finetuning

이차 할당 문제(QAP)는 근본적인 NP-hard 문제로서, 기존의 휴리스틱 방법과 최신 머신러닝 기반 솔버 모두에게 상당한 어려움을 야기합니다. 기존의 QAP 솔버는 여전히 구조적으로 다양한 실제 문제에 대해 일관되게 경쟁력 있는 성능을 달성하는 데 어려움을 겪고 있습니다. 이러한 성능 격차를 해소하기 위해, 우리는 혁신적인 순열 학습 프레임워크인 PLMA를 제안합니다. PLMA는 효율적인 웜 스타팅 MCMC 미세 조정 절차를 통해 배포 시간 성능을 향상시키며, 짧은 마르코프 체인을 활용하여 이전에 탐색된 유망한 영역에 적응을 고정합니다. 순열 공간에 대한 빠른 탐색을 위해, 우리는 $O(1)$ 시간의 2-swap Metropolis-Hastings 샘플링 단계를 가능하게 하는 가산 에너지 기반 모델(EBM)을 설계했습니다. 또한, EBM을 매개변수화하는 데 사용되는 신경망은 QAP에서 시설과 위치 간의 상호 작용을 모델링하기 위한 확장 가능하고 유연한 크로스-그래프 어텐션 메커니즘을 통합합니다. 광범위한 실험 결과, PLMA는 다양한 벤치마크에서 최첨단 기준 모델보다 일관되게 뛰어난 성능을 보임을 보여줍니다. 특히, PLMA는 QAPLIB에서 평균 최적성 격차가 거의 0에 가깝고, 악명 높은 Taixxeyy 인스턴스에서 놀랍도록 뛰어난 견고성을 보여주며, 또한 대역폭 최소화 문제에 효과적인 QAP 솔버로 사용될 수 있습니다.

The quadratic assignment problem (QAP) is a fundamental NP-hard task that poses significant challenges for both traditional heuristics and modern learning-based solvers. Existing QAP solvers still struggle to achieve consistently competitive performance across structurally diverse real-world instances. To bridge this performance gap, we propose PLMA, an innovative permutation learning framework. PLMA features an efficient warm-started MCMC finetuning procedure to enhance deployment-time performance, leveraging short Markov chains to anchor the adaptation to the promising regions previously explored. For rapid exploration via MCMC over the permutation space, we design an additive energy-based model (EBM) that enables an $O(1)$-time 2-swap Metropolis-Hastings sampling step. Moreover, the neural network used to parameterize the EBM incorporates a scalable and flexible cross-graph attention mechanism to model interactions between facilities and locations in the QAP. Extensive experiments demonstrate that PLMA consistently outperforms state-of-the-art baselines across various benchmarks. In particular, PLMA achieves a near-zero average optimality gap on QAPLIB, exhibits remarkably superior robustness on the notoriously difficult Taixxeyy instances, and also serves as an effective QAP solver in bandwidth minimization.