論文の概要: Provably Data-driven Lagrangian Relaxation for Mixed Integer Linear Programming

• arxiv url: http://arxiv.org/abs/2605.19052v1
• Date: Mon, 18 May 2026 19:16:42 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-20 15:03:08.959757
• Title: Provably Data-driven Lagrangian Relaxation for Mixed Integer Linear Programming
• Title（参考訳）: 混合整数線形計画法におけるデータ駆動ラグランジアン緩和の可能性
• Authors: Tung Quoc Le, Anh Tuan Nguyen, Viet Anh Nguyen,
• Abstract要約: ラグランジアン緩和(Lagrangian Relaxation, LR)は、MILP(Mixed Linear Programming)を解くための強力な手法である。 結合制約を緩和することにより、LRは並列サブプロブレム解を可能とし、しばしば通常の線形プログラミング緩和よりも厳密な双対境界を与える。 最近の実証研究は、これらの緩和を予測するために機械学習を用いた有望な結果を示しているが、そのような手法の理論的な理解は依然として未解決のままである。
• 参考スコア（独自算出の注目度）: 16.202112411377893
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Lagrangian Relaxation (LR) is a powerful technique for solving large-scale Mixed Integer Linear Programming (MILP), particularly those with decomposable structures, such as vehicle routing or unit commitment problems. By relaxing the coupling constraints, LR enables parallel subproblem solving and often yields tighter dual bounds than standard linear programming relaxations, which is crucial for efficient branch-and-bound pruning. While recent empirical work has shown promising results using machine learning to predict these multipliers, a theoretical understanding of such methods remains an open question. In this work, we bridge this gap by analyzing the problem of learning LR through the lens of Data-driven Algorithm Design, i.e., a statistical learning problem over a distribution of problem instances. Our contributions are as follows: first, we derive a generalization bound of $\mathcal{O}(s^{1.5}/\sqrt{N})$ for the learned multipliers, where $s$ is the number of coupling constraints and $N$ is the sample size. Second, we provide a minimax lower-bound of $Ω(s/\sqrt{N})$, proving that a linear dependency is unavoidable. Third, we constructively close this theoretical gap by proving that Stochastic Gradient Ascent (SGA) with averaging achieves the minimax optimal rate $Θ(s/\sqrt{N})$. Finally, we extend our framework to the learning-to-warm-start setting, proving that it achieves a fast, minimax-optimal rate of $Θ(s/N)$ and establishing a theoretical advantage over direct multiplier prediction.
• Abstract（参考訳）: ラグランジアン緩和(Lagrangian Relaxation, LR)は、大規模な混合整数線形計画法(MILP)を解くための強力な手法である。 結合制約を緩和することにより、LRは並列サブプロブレム解を可能にし、しばしば分岐とバウンドの効率的なプルーニングに欠かせない通常の線形プログラミング緩和よりも厳密な双対境界を与える。 最近の実証研究は、これらの乗数を予測するために機械学習を用いた有望な結果を示しているが、そのような手法の理論的な理解は依然として未解決のままである。 本研究では,データ駆動型アルゴリズム設計のレンズを用いてLR学習の問題,すなわち問題インスタンスの分布に関する統計的学習問題を解析することにより,このギャップを埋める。 まず、学習した乗数に対して$\mathcal{O}(s^{1.5}/\sqrt{N})$の一般化境界を導出します。 第二に、線型依存が避けられないことを証明する$Ω(s/\sqrt{N})$のミニマックスローバウンドを提供する。 第三に、SGA(Stochastic Gradient Ascent)が平均値を持つような理論的なギャップは、極小極小値の最大速度を$(s/\sqrt{N})$とすることを示すことによって、この理論的ギャップを建設的に閉じる。 最後に、我々のフレームワークを学習からウォームスタートの設定にまで拡張し、より高速で最小限の最適化率を$(s/N)$で達成し、直接乗算器予測よりも理論的優位性を確立することを証明した。

関連論文リスト

• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  基本的で長期にわたる課題は、その効率的な近似である。 一般に用いられるすべての半値に対して$P(|hatboldsymbol-boldsymbol|_2geq)leq$を必要とする線形空間アルゴリズムを開発する。 本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。
  論文  参考訳（メタデータ） (2026-04-09T16:38:14Z)
• Closing the Approximation Gap of Partial AUC Optimization: A Tale of Two Formulations [121.39938773554523]
  ROC曲線の下の領域(AUC)は、クラス不均衡と決定制約の両方を持つ実世界のシナリオにおける重要な評価指標である。 PAUC最適化の近似ギャップを埋めるために,2つの簡単なインスタンス単位のミニマックス修正を提案する。 得られたアルゴリズムは、サンプルサイズと典型的な一方方向と双方向のPAUCに対して$O(-2/3)$の収束率の線形パーイテレーション計算複雑性を享受する。
  論文  参考訳（メタデータ） (2025-12-01T02:52:33Z)
• Offline Reinforcement Learning via Linear-Programming with Error-Bound Induced Constraints [26.008426384903764]
  オフライン強化学習(RL)は、事前に収集されたデータセットを使用して、マルコフ決定プロセス(MDP)の最適ポリシーを見つけることを目的としている。 本研究では,オフラインRLにおけるマルコフ決定過程の線形プログラミング (LP) の再検討を行う。
  論文  参考訳（メタデータ） (2022-12-28T15:28:12Z)
• Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning [52.76230802067506]
  漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。 提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。 初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
  論文  参考訳（メタデータ） (2021-10-09T21:13:48Z)
• Sparse Plus Low Rank Matrix Decomposition: A Discrete Optimization Approach [6.952045528182883]
  スパースプラス低ランク分解問題(SLR)について検討する。 SLRはオペレーションリサーチと機械学習の基本的な問題である。 本稿では,SLRの新たな定式化を導入し,その基礎となる離散性をモデル化する。
  論文  参考訳（メタデータ） (2021-09-26T20:49:16Z)
• Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity [67.02490430380415]
  モデルに基づくMARLは、Nash平衡値(NE)を求めるために$tilde O(|S||B|(gamma)-3epsilon-2)$のサンプル複雑性を実現する。 また、アルゴリズムが報酬に依存しない場合、そのようなサンプル境界は最小値(対数因子まで)であり、アルゴリズムは報酬知識のない遷移サンプルを問合せする。
  論文  参考訳（メタデータ） (2020-07-15T03:25:24Z)
• Computationally efficient sparse clustering [67.95910835079825]
  我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。 ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
  論文  参考訳（メタデータ） (2020-05-21T17:51:30Z)
• New Bounds For Distributed Mean Estimation and Variance Reduction [25.815612182815702]
  本稿では,ローカルな$d$-dimensional vector $x_v を mathbbRd$ で与えられた$n$マシンが分散平均推定(DME)問題を考える。 提案手法は, 従来の手法と比較して, 応用の実践的改善をもたらすことを示す。
  論文  参考訳（メタデータ） (2020-02-21T13:27:13Z)

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

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