ウォームスタート付きMCMC微調整による二次割当問題の解法学習
arXiv cs.LG / 2026/4/23
📰 ニュースModels & Research
要点
- 本論文は、二次割当問題（QAP）を扱い、NP困難性により、従来の手法や学習ベースの解法が多様な実世界インスタンスで一貫して高性能を出すことが難しいという課題に取り組んでいます。
- 提案手法PLMAは、短いマルコフ連鎖を用いたウォームスタート付きMCMC微調整によって、導入時の性能を改善する順列学習フレームワークです。
- PLMAでは、加法型エネルギーベースモデル（EBM）を設計し、順列空間でのMCMC探索を効率化するために2スワップのMetropolis–HastingsサンプリングをO(1)時間で行えるようにしています。
- EBMのニューラルなパラメータ化には、QAPにおける「施設」と「場所」の相互作用を捉えるスケーラブルなクロスグラフ注意機構が用いられています。
- 実験ではPLMAが最先端ベースラインを一貫して上回り、特にQAPLIBで平均最適性ギャップがほぼゼロ、難解なTaixxeyyインスタンスでの頑健性が高いこと、さらに帯域最小化にも有効であることが示されています。
