論文の概要: Influence branching for learning to solve mixed-integer programs online

• arxiv url: http://arxiv.org/abs/2510.04273v1
• Date: Sun, 05 Oct 2025 16:29:44 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-07 16:52:59.55228
• Title: Influence branching for learning to solve mixed-integer programs online
• Title（参考訳）: 混合整数プログラムのオンライン学習における分岐の影響
• Authors: Paul Strang, Zacharie Alès, Côme Bissuel, Olivier Juan, Safia Kedad-Sidhoum, Emmanuel Rachelson,
• Abstract要約: この研究は、オンラインのMIPを解決するための新しいアプローチを導入している。 新しいグラフ指向の変数選択戦略であるイニシアティブブランチは、ブランチとバウンドアルゴリズムの最初のイテレーションを通じて適用されます。 オンライン学習手法の現状に匹敵する結果が得られる。
• 参考スコア（独自算出の注目度）: 4.802758600019421
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: On the occasion of the 20th Mixed Integer Program Workshop's computational competition, this work introduces a new approach for learning to solve MIPs online. Influence branching, a new graph-oriented variable selection strategy, is applied throughout the first iterations of the branch and bound algorithm. This branching heuristic is optimized online with Thompson sampling, which ranks the best graph representations of MIP's structure according to computational speed up over SCIP. We achieve results comparable to state of the art online learning methods. Moreover, our results indicate that our method generalizes well to more general online frameworks, where variations in constraint matrix, constraint vector and objective coefficients can all occur and where more samples are available.
• Abstract（参考訳）: 第20回Mixed Integer Program Workshopの計算コンペティションでは,MIPをオンラインで解くための新たなアプローチが導入された。 新しいグラフ指向の変数選択戦略であるインフルエンス分岐は、ブランチとバウンドアルゴリズムの最初のイテレーションを通して適用される。 この分岐ヒューリスティックはトンプソンサンプリングによってオンラインで最適化され、SCIPの計算速度に応じてMIPの構造の最良のグラフ表現をランク付けする。 我々は、最先端のオンライン学習手法に匹敵する結果を得る。 さらに,本手法は,制約行列,制約ベクトル,目的係数の変動がすべて発生し,より多くのサンプルが利用可能となるような,より一般的なオンラインフレームワークによく応用できることを示す。

関連論文リスト

• Online Network Source Optimization with Graph-Kernel MAB [62.6067511147939]
  大規模ネットワークにおける最適なソース配置をオンラインで学習するためのグラフカーネルマルチアームバンディットアルゴリズムであるGrab-UCBを提案する。 適応グラフ辞書モデルを用いて,ネットワークプロセスを記述する。 我々は、ネットワークパラメータに依存する性能保証を導出し、シーケンシャルな意思決定戦略の学習曲線にさらに影響を及ぼす。
  論文  参考訳（メタデータ） (2023-07-07T15:03:42Z)
• Data-driven Mixed Integer Optimization through Probabilistic Multi-variable Branching [8.03915440701838]
  オンライン混合整数プログラム(MIP)をオフラインデータセットと機械学習モデルで高速化する事前学習混合最適化フレームワーク(PreMIO)を提案する。 本手法は, 濃度不等式から選択した超平面を用いて, 実現可能な領域を分割するデータ駆動型多変量基数分岐法に基づく。
  論文  参考訳（メタデータ） (2023-05-21T05:11:30Z)
• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。 微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
  論文  参考訳（メタデータ） (2023-02-24T18:41:48Z)
• Branch Ranking for Efficient Mixed-Integer Programming via Offline Ranking-based Policy Learning [45.1011106869493]
  オフライン強化学習(RL)問題として分岐学習を定式化する。 オフラインポリシー学習を通じてブランチランキングと呼ばれるブランチモデルをトレーニングします。 合成MIPベンチマークと実世界のタスクの実験は、ブランチランクがより効率的で堅牢であることを示している。
  論文  参考訳（メタデータ） (2022-07-26T15:34:10Z)
• On the Convergence of Distributed Stochastic Bilevel Optimization Algorithms over a Network [55.56019538079826]
  バイレベル最適化は、幅広い機械学習モデルに適用されている。 既存のアルゴリズムの多くは、分散データを扱うことができないように、シングルマシンの設定を制限している。 そこで我々は,勾配追跡通信機構と2つの異なる勾配に基づく分散二段階最適化アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-06-30T05:29:52Z)
• Deep Reinforcement Learning for Exact Combinatorial Optimization: Learning to Branch [13.024115985194932]
  本稿では、強化学習(RL)パラダイムを用いた最適化において、データラベリングと推論の問題を解決するための新しいアプローチを提案する。 我々は模倣学習を用いてRLエージェントをブートストラップし、PPO(Proximal Policy)を使用してグローバルな最適なアクションを探索する。
  論文  参考訳（メタデータ） (2022-06-14T16:35:58Z)
• A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs [91.07247251502564]
  本稿では,2つの世界の長所を結合するハイブリッドな手法を提案する。この手法では,グラフを最適化する上層学習手法とバイレベルフレームワークを開発する。 このような二段階のアプローチは、元のハードCOでの学習を単純化し、モデルキャパシティの需要を効果的に軽減することができる。
  論文  参考訳（メタデータ） (2021-06-09T09:18:18Z)
• Reinforcement Learning for Variable Selection in a Branch and Bound Algorithm [0.10499611180329801]
  現実世界のインスタンスのパターンを活用して、与えられた問題に最適化された新しいブランチ戦略をスクラッチから学習します。 本稿では,この課題に特化して設計された新しい強化学習手法であるFMSTSを提案する。
  論文  参考訳（メタデータ） (2020-05-20T13:15:48Z)
• Optimization of Graph Total Variation via Active-Set-based Combinatorial Reconditioning [48.42916680063503]
  本稿では,この問題クラスにおける近位アルゴリズムの適応型事前条件付け手法を提案する。 不活性エッジのネスト・フォレスト分解により局所収束速度が保証されることを示す。 この結果から,局所収束解析は近似アルゴリズムにおける可変指標選択の指針となることが示唆された。
  論文  参考訳（メタデータ） (2020-02-27T16:33:09Z)

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

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