論文の概要: Learning to Solve the Quadratic Assignment Problem with Warm-Started MCMC Finetuning

• arxiv url: http://arxiv.org/abs/2604.20109v1
• Date: Wed, 22 Apr 2026 02:13:23 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-23 15:36:10.919021
• Title: Learning to Solve the Quadratic Assignment Problem with Warm-Started MCMC Finetuning
• Title（参考訳）: ウォームスタートMCMCファインタニングによる二次割当問題の解法
• Authors: Yicheng Pan, Ruisong Zhou, Haijun Zou, Tianyou Li, Zaiwen Wen,
• Abstract要約: 二次代入問題(QAP)は、伝統的なタイスと現代の学習に基づく解法の両方に重大な課題をもたらす基本的なNPハードタスクである。 この性能ギャップを埋めるため,革新的な置換学習フレームワークPLMAを提案する。 PLMAは、様々なベンチマークにおいて、最先端のベースラインを一貫して上回ることを示す。
• 参考スコア（独自算出の注目度）: 6.4295448922921326
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.
• Abstract（参考訳）: 二次代入問題(QAP)は、従来のヒューリスティックと現代の学習に基づく解法の両方に重大な課題を提起する基本的なNPハード問題である。 既存のQAPソルバは、構造的に多様な実世界のインスタンス間で一貫して競合するパフォーマンスを達成するのに依然として苦労している。 この性能ギャップを埋めるため,革新的な置換学習フレームワークPLMAを提案する。 PLMAは、デプロイ時のパフォーマンスを向上させるための効率的なウォームスタートMCMC微調整手順を備えており、短いマルコフ連鎖を利用して、これまで検討されていた将来性のある領域への適応を固定している。 置換空間上でのMCMCによる迅速な探索のために、O(1)$-time 2-swap Metropolis-Hastingsサンプリングステップを可能にする追加エネルギーベースモデル(EBM)を設計する。 さらに、ESMのパラメータ化に使われるニューラルネットワークには、スケーラブルで柔軟なクロスグラフアテンション機構が組み込まれており、QAP内の施設と場所間の相互作用をモデル化している。 PLMAは様々なベンチマークで常に最先端のベースラインを上回っている。 特に、PLMAはQAPLIB上の平均最適値のほぼゼロのギャップを達成し、非常に難しいTaixxeyyインスタンスに対して極めて優れたロバスト性を示し、また帯域幅最小化において効果的なQAP解決器として機能する。

関連論文リスト

• Plug, Play, and Fortify: A Low-Cost Module for Robust Multimodal Image Understanding Models [6.350443894942629]
  MWAM(Multimodal Weight Allocation Module)は、トレーニング中の各ブランチのコントリビューションを動的に再バランスするプラグイン・アンド・プレイコンポーネントである。 MWAMは幅広いタスクとモダリティの組み合わせで一貫したパフォーマンス向上を実現している。
  論文  参考訳（メタデータ） (2026-02-26T05:51:41Z)
• Adaptive Linear Path Model-Based Diffusion [52.84663832658799]
  リニアパスモデルベース拡散(LP-MBD)を導入し、分散保存スケジュールをフローマッチング線形確率パスに置き換える。 また,適応型LP-MBD(ALP-MBD)を提案し,タスクの複雑さや環境条件に応じて拡散ステップやノイズレベルを調整する。
  論文  参考訳（メタデータ） (2026-02-02T21:33:03Z)
• ARES: Multimodal Adaptive Reasoning via Difficulty-Aware Token-Level Entropy Shaping [54.37497695483689]
  本稿では,タスクの難易度に基づいて探索作業を動的に割り当てる適応推論のための統合フレームワークであるARESを提案する。 単一トークンエントロピーはノイズが多いが,高いウィンドウエントロピー(HWE)トークンは推論クリティカルな瞬間を確実に捉えることができる。 In the Adaptive Cold-Start stage, we curate multimodal and textual data paired with reasoning traces of length proportional to problem difficulty。 第2段階では,HWEトークンを探索トリガとする適応エントロピーポリシー最適化(AEPO)を開発する。
  論文  参考訳（メタデータ） (2025-10-09T17:03:28Z)
• Mix-QSAM: Mixed-Precision Quantization of the Segment Anything Model [0.0]
  Mix-QSAMはSegment Anything Model(SAM)のためのPTQフレームワークである。 モデル出力に対する各レイヤの寄与を定量化するために,Kulback-Leibler (KL) 偏差を用いて導出したレイヤ単位の重要度スコアを導入する。 また、隣接層間の依存関係を捉えるために、因果的相互情報に基づく新しい計量である層間相乗法を導入する。
  論文  参考訳（メタデータ） (2025-05-08T00:08:31Z)
• Entropy-Regularized Token-Level Policy Optimization for Language Agent Reinforcement [67.1393112206885]
  大規模言語モデル(LLM)は、対話的な意思決定タスクにおいてインテリジェントなエージェントとして期待されている。 本稿では,トークンレベルでのLLMの最適化に適したエントロピー拡張RL法である,エントロピー正規化トークンレベル最適化(ETPO)を導入する。 我々は,データサイエンスコード生成を多段階対話型タスクのシリーズとしてモデル化したシミュレーション環境におけるETPOの有効性を評価する。
  論文  参考訳（メタデータ） (2024-02-09T07:45:26Z)
• Learning Energy-Based Prior Model with Diffusion-Amortized MCMC [89.95629196907082]
  非収束短距離MCMCを用いた事前及び後方サンプリングによる潜時空間EMM学習の一般的な実践は、さらなる進歩を妨げている。 本稿では,MCMCサンプリングのための単純だが効果的な拡散型アモータイズ手法を導入し,それに基づく潜時空間EMMのための新しい学習アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2023-10-05T00:23:34Z)
• Collaborative Intelligent Reflecting Surface Networks with Multi-Agent Reinforcement Learning [63.83425382922157]
  インテリジェント・リフレクション・サーフェス(IRS)は将来の無線ネットワークに広く応用されることが想定されている。 本稿では,エネルギー収穫能力を備えた協調型IRSデバイスを用いたマルチユーザ通信システムについて検討する。
  論文  参考訳（メタデータ） (2022-03-26T20:37:14Z)
• No MCMC for me: Amortized sampling for fast and stable training of energy-based models [62.1234885852552]
  エネルギーベースモデル(EBM)は、不確実性を表す柔軟で魅力的な方法である。 本稿では,エントロピー規則化ジェネレータを用いてEMMを大規模に訓練し,MCMCサンプリングを記憶する簡単な方法を提案する。 次に、最近提案されたジョイント・エナジー・モデル(JEM)に推定器を適用し、元の性能と高速で安定したトレーニングとを一致させる。
  論文  参考訳（メタデータ） (2020-10-08T19:17:20Z)
• Improving the Performance of Stochastic Local Search for Maximum Vertex Weight Clique Problem Using Programming by Optimization [21.407603070913588]
  我々はMVWCPを解くための新しい、柔軟で高パラメトリックなフレームワークを開発した。 我々は、MVWCPを広範囲の顕著なベンチマークで解く上で、最先端の進歩を実現している。
  論文  参考訳（メタデータ） (2020-02-27T04:22:19Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。