論文の概要: Generalization Guarantees for Learning Branch-and-Cut Policies in Integer Programming

• arxiv url: http://arxiv.org/abs/2505.11636v1
• Date: Fri, 16 May 2025 19:00:02 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-20 14:57:10.755619
• Title: Generalization Guarantees for Learning Branch-and-Cut Policies in Integer Programming
• Title（参考訳）: 整数プログラミングにおける分岐とカットの政策学習のための一般化保証
• Authors: Hongyu Cheng, Amitabh Basu,
• Abstract要約: 混合整数プログラミング(MIP)は最適化問題のための強力なフレームワークを提供する。 ブランチ・アンド・カット (B&C) は最先端の解法において主要なアルゴリズムである。
• 参考スコア（独自算出の注目度）: 1.1510009152620668
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Mixed-integer programming (MIP) provides a powerful framework for optimization problems, with Branch-and-Cut (B&C) being the predominant algorithm in state-of-the-art solvers. The efficiency of B&C critically depends on heuristic policies for making sequential decisions, including node selection, cut selection, and branching variable selection. While traditional solvers often employ heuristics with manually tuned parameters, recent approaches increasingly leverage machine learning, especially neural networks, to learn these policies directly from data. A key challenge is to understand the theoretical underpinnings of these learned policies, particularly their generalization performance from finite data. This paper establishes rigorous sample complexity bounds for learning B&C policies where the scoring functions guiding each decision step (node, cut, branch) have a certain piecewise polynomial structure. This structure generalizes the linear models that form the most commonly deployed policies in practice and investigated recently in a foundational series of theoretical works by Balcan et al. Such piecewise polynomial policies also cover the neural network architectures (e.g., using ReLU activations) that have been the focal point of contemporary practical studies. Consequently, our theoretical framework closely reflects the models utilized by practitioners investigating machine learning within B&C, offering a unifying perspective relevant to both established theory and modern empirical research in this area. Furthermore, our theory applies to quite general sequential decision making problems beyond B&C.
• Abstract（参考訳）: 混合整数プログラミング(MIP)は最適化問題のための強力なフレームワークを提供する。 B&Cの効率は、ノードの選択、カットの選択、分岐変数の選択を含むシーケンシャルな決定を行うためのヒューリスティックなポリシーに大きく依存する。 従来の問題解決者は手動で調整されたパラメータを持つヒューリスティックスを採用することが多いが、最近のアプローチでは、機械学習、特にニューラルネットワークを活用して、これらのポリシーを直接データから学習するようになっている。 鍵となる課題は、これらの学習されたポリシーの理論的基盤、特に有限データからの一般化性能を理解することである。 本稿では, 各決定ステップ(ノード, カット, 分岐)を導くスコアリング関数が, ある程度の多項式構造を持つB&Cポリシーを学習するために, 厳密なサンプル複雑性境界を確立する。 この構造は、実際に最も一般的に展開されたポリシーを形成する線形モデルを一般化し、最近バルカンらによる一連の理論的研究において、現代の実践研究の焦点となったニューラルネットワークアーキテクチャ(例えば、ReLUアクティベーション)についても研究されている。 この理論枠組みは,B&C内での機械学習の実践者が活用するモデルに密接に反映しており,この領域における確立された理論と近代的な実証研究の両方に関連する統一的な視点を提供する。 さらに、我々の理論は、B&Cを超えて、非常に一般的なシーケンシャルな意思決定問題に適用できる。

関連論文リスト

• Decision-focused Graph Neural Networks for Combinatorial Optimization [62.34623670845006]
  最適化問題に取り組むための新たな戦略は、従来のアルゴリズムに代わるグラフニューラルネットワーク(GNN)の採用である。 GNNや従来のアルゴリズムソルバがCOの領域で人気が高まっているにもかかわらず、それらの統合利用とエンドツーエンドフレームワークにおけるそれらの相関について限定的な研究がなされている。 我々は、GNNを利用してCO問題に補助的なサポートで対処する決定に焦点を当てたフレームワークを導入する。
  論文  参考訳（メタデータ） (2024-06-05T22:52:27Z)
• Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-Constraint [56.74058752955209]
  本稿では,RLHFによる強化学習を用いた生成モデルのアライメント過程について検討する。 まず、オフラインPPOやオフラインDPOのような既存の一般的な手法の主な課題を、環境の戦略的探索に欠如していると認識する。 有限サンプル理論保証を用いた効率的なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-18T18:58:42Z)
• Unified Algorithms for RL with Decision-Estimation Coefficients: PAC, Reward-Free, Preference-Based Learning, and Beyond [28.118197762236953]
  我々は,大規模な学習目標のための統一的なアルゴリズムフレームワークを開発する。 我々のフレームワークは、非回帰RL、PAC RL、報酬なし学習、モデル推定、嗜好に基づく学習など、多くの学習目標を処理する。 応用として、一般化されたDECを有界化するための自然な十分条件として「分解可能表現」を提案する。
  論文  参考訳（メタデータ） (2022-09-23T17:47:24Z)
• Contextualize Me -- The Case for Context in Reinforcement Learning [49.794253971446416]
  文脈強化学習(cRL)は、このような変化を原則的にモデル化するためのフレームワークを提供する。 我々は,cRLが有意義なベンチマークや一般化タスクに関する構造化推論を通じて,RLのゼロショット一般化の改善にどのように貢献するかを示す。
  論文  参考訳（メタデータ） (2022-02-09T15:01:59Z)
• A Subgame Perfect Equilibrium Reinforcement Learning Approach to Time-inconsistent Problems [4.314956204483074]
  我々は,時間一貫性(TIC)問題に対するサブゲーム完全均衡強化学習フレームワークを構築した。 我々は,SPERLを解き,両課題に対処する,BPI(backward Policy iteration)と呼ばれるアルゴリズムの新たなクラスを提案する。 トレーニングフレームワークとしてのBPIの実用性を実証するため,標準的なRLシミュレーション手法を適用し,2つのBPIベースのトレーニングアルゴリズムを導出する。
  論文  参考訳（メタデータ） (2021-10-27T09:21:35Z)
• Developing Constrained Neural Units Over Time [81.19349325749037]
  本稿では,既存のアプローチと異なるニューラルネットワークの定義方法に焦点をあてる。 ニューラルネットワークの構造は、データとの相互作用にも拡張される制約の特別なクラスによって定義される。 提案した理論は時間領域にキャストされ, データを順序づけられた方法でネットワークに提示する。
  論文  参考訳（メタデータ） (2020-09-01T09:07:25Z)
• Continuous Action Reinforcement Learning from a Mixture of Interpretable Experts [35.80418547105711]
  本稿では,複雑な関数近似を内部値予測に保持するポリシスキームを提案する。 この論文の主な技術的貢献は、この非微分不可能な状態選択手順によってもたらされた課題に対処することである。
  論文  参考訳（メタデータ） (2020-06-10T16:02:08Z)

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

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