論文の概要: The Proxy Benders Decomposition

• arxiv url: http://arxiv.org/abs/2606.07403v1
• Date: Fri, 05 Jun 2026 15:47:08 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-08 14:33:29.834952
• Title: The Proxy Benders Decomposition
• Title（参考訳）: Proxy Benders分解
• Authors: Changkun Guan, El Mehdi Er Raqabi, Mathieu Tanneau, Pascal Van Hentenryck,
• Abstract要約: 本稿では,大規模混合整数最適化問題に対する新しい分解フレームワークであるプロキシベンダー分解(Proxy-BD)を紹介する。 提案するプロキシは,有意なBendersカットを生成するための2つの実現可能なソリューションを生成する,自己教師付き予測プロジェクト・アンド・コンプリート機構に従う。 大規模施設配置とネットワーク設計に関する実験により, Proxy-BD はサブプロブレムの計算労力を大幅に削減することが示された。
• 参考スコア（独自算出の注目度）: 16.08090449490226
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Benders decomposition is a fundamental framework for solving large-scale mixed-integer optimization problems with complicating variables that, when fixed, yield significantly easier subproblems. However, classical Benders decomposition repeatedly solves highly similar subproblems and often exhibits zigzagging behavior across iterations, leading to slow convergence in large-scale settings. Motivated by the repetitive structure and parametric nature of Benders subproblems, this paper introduces the proxy Benders decomposition (Proxy-BD), a new decomposition framework in which subproblem optimization is replaced by certified optimization proxies rather than repeated exact solves. The proposed proxy follows a self-supervised predict-project-and-complete mechanism that produces dual-feasible solutions for generating provably valid Benders cuts. The framework preserves the theoretical validity of the decomposition independently of prediction quality through a projection-and-completion certification layer. A formal characterization of proxy-induced cuts is established, and the framework naturally extends to modern decomposition schemes, including branch-and-Benders-cut algorithms. Computational experiments on large-scale facility location and network design problems demonstrate that Proxy-BD substantially reduces the computational effort of subproblems while maintaining near-optimal solution quality. On large-scale uncapacitated facility location instances up to 2000x2000, Proxy-BD achieves median optimality gaps below 0.5%, yields up to 161x median speedups, and reduces the number of generated cuts by more than 240x on the largest instances. The computational gains consistently increase with recourse complexity, indicating that proxy-based inference scales substantially more favorably than repeated exact subproblem optimization in large-scale decomposition settings.
• Abstract（参考訳）: ベンダー分解(Benders decomposition)は、大規模な混合整数最適化問題を解決するための基本的なフレームワークである。 しかし、古典的ベンダー分解は、非常に類似したサブプロブレムを繰り返し解決し、しばしば繰り返しにわたってジグザグの振る舞いを示すため、大規模な設定では収束が遅くなる。 本稿では, Benders サブプロブレムの繰り返し構造とパラメトリック特性に触発され, プロキシ Benders 分解 (Proxy-BD) を導入する。 提案するプロキシは,有意なBendersカットを生成するための2つの実現可能なソリューションを生成する,自己教師付き予測プロジェクト・アンド・コンプリート機構に従う。 このフレームワークは、予測・補完認証層を介して予測品質とは無関係に分解の理論的妥当性を保持する。 プロキシによって引き起こされるカットの形式的特徴が確立され、このフレームワークはブランチ・アンド・ベンダー・カットアルゴリズムを含む現代的な分解スキームに自然に拡張される。 大規模施設配置問題とネットワーク設計問題に関する計算実験により, Proxy-BD は近似解の品質を維持しながらサブプロブレムの計算労力を大幅に削減することを示した。 2000×2000までの大規模非容量施設では、プロキシ-BDは0.5%以下で中央値の最適性ギャップを達成し、中央値のスピードアップを161倍にし、最大値のカット数を240倍以上に削減する。 計算ゲインはリコースの複雑さとともに一貫して増加し、プロキシベースの推論は大規模な分解設定において、繰り返しの正確なサブプロブレム最適化よりもかなり好意的にスケールすることを示す。

関連論文リスト

• Implicit Binarization via Complex Phase Dynamics in Combinatorial Optimization [5.3548017019682]
  そこで本研究では,NP硬化型最適化問題に対する解法を大幅に改善する,物理に着想を得た連続緩和フレームワークを提案する。 大規模QUBOMP構成では,重音速でゼロ誤差を達成できた。
  論文  参考訳（メタデータ） (2026-05-23T10:18:58Z)
• Towards Robust Scaling Laws for Optimizers [89.21160945066737]
  経験的スケーリング法則は、モデルのサイズやトレーニングデータの増加に伴って損失を予測するために広く使用されている。 本研究では, 損失分解を既約, 近似, 最適化誤差に分解した結果, チンチラ方式のスケーリング法則が自然に現れることを示す。
  論文  参考訳（メタデータ） (2026-02-07T21:40:33Z)
• ARMOR: High-Performance Semi-Structured Pruning via Adaptive Matrix Factorization [99.96330641363396]
  ARMOR: (Adaptive Representation with Matrix-factorization) は、新しい1ショットのポストトレーニングプルーニングアルゴリズムである。 ARMORは重量を直接刈る代わりに、各重量行列を2:4のスパースコアに分解する。 ARMORは、幅広いダウンストリームタスクとパープレキシティ評価において、最先端の2:4プルーニング手法よりも一貫して、はるかに優れています。
  論文  参考訳（メタデータ） (2025-10-07T02:39:20Z)
• Adaptive Sampled Softmax with Inverted Multi-Index: Methods, Theory and Applications [79.53938312089308]
  MIDX-Samplerは、逆多重インデックスアプローチに基づく新しい適応型サンプリング戦略である。 本手法は, サンプリングバイアス, 勾配バイアス, 収束速度, 一般化誤差境界などの重要な問題に対処するため, 厳密な理論的解析によって裏付けられている。
  論文  参考訳（メタデータ） (2025-01-15T04:09:21Z)
• l1-norm regularized l1-norm best-fit lines [3.0963566281269594]
  簡単な比率とソート手法を用いた新しいフィッティング法を提案する。 提案アルゴリズムは、O$(n2 m log n)$の最悪の時間複雑性を示し、ある場合にはスパース部分空間に対する大域的最適性を達成する。
  論文  参考訳（メタデータ） (2024-02-26T16:30:58Z)
• Accelerating L-shaped Two-stage Stochastic SCUC with Learning Integrated Benders Decomposition [0.0]
  本稿では,二段階セキュリティ制約付き単位コミットメント問題の解法として,Benders分解の強化版を提案する。 目標は、より厳密なカットを作成し、マスター問題のサイズを小さくすることで、Benders分解の計算コストとメモリ使用量を削減することである。
  論文  参考訳（メタデータ） (2023-11-17T19:31:40Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• Factorization of Multi-Agent Sampling-Based Motion Planning [72.42734061131569]
  現代のロボティクスは、共有環境内で複数のエンボディエージェントを動作させることが多い。 標準的なサンプリングベースのアルゴリズムは、ロボットの関節空間における解の探索に使用できる。 我々は、因子化の概念をサンプリングベースアルゴリズムに統合し、既存の手法への最小限の変更しか必要としない。 本稿では, PRM* のサンプル複雑性の観点から解析的ゲインを導出し, RRG の実証結果を示す。
  論文  参考訳（メタデータ） (2023-04-01T15:50:18Z)
• STRIDE along Spectrahedral Vertices for Solving Large-Scale Rank-One Semidefinite Relaxations [27.353023427198806]
  我々は、制約のない最適化問題(POP)の高次半定値プログラミング緩和を考察する。 POPから独立してSDPを解く既存のアプローチは、そのようなSDPの典型的な非エネルギー性のため、大きな問題にスケールできないか、あるいは緩やかな収束に苦しむことができない。 我々は SpecTrahedral vErtices (STRIDE) と呼ばれる新しいアルゴリズムフレームワークを提案する。
  論文  参考訳（メタデータ） (2021-05-28T18:07:16Z)
• Two-Stage Stochastic Optimization via Primal-Dual Decomposition and Deep Unrolling [86.85697555068168]
  2段階のアルゴリズム最適化は、様々な工学や科学的応用において重要な役割を果たす。 特に長期変数と短期変数が制約の中で結合されている場合、アルゴリズムは効率的ではない。 PDD-SSCAが既存のソリューションよりも優れたパフォーマンスを達成できることを示します。
  論文  参考訳（メタデータ） (2021-05-05T03:36:00Z)
• Distributionally Robust Bayesian Optimization [121.71766171427433]
  そこで本研究では,ゼロ次雑音最適化のための分散ロバストなベイズ最適化アルゴリズム(DRBO)を提案する。 提案アルゴリズムは, 種々の設定において, 線形に頑健な後悔を確実に得る。 提案手法は, 実世界のベンチマークと実世界のベンチマークの両方において, 頑健な性能を示す。
  論文  参考訳（メタデータ） (2020-02-20T22:04:30Z)

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

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