論文の概要: Reinforcement Learning for Variable Selection in a Branch and Bound Algorithm

• arxiv url: http://arxiv.org/abs/2005.10026v1
• Date: Wed, 20 May 2020 13:15:48 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-01 04:56:06.941817
• Title: Reinforcement Learning for Variable Selection in a Branch and Bound Algorithm
• Title（参考訳）: 分岐境界アルゴリズムにおける可変選択のための強化学習
• Authors: Marc Etheve and Zacharie Al\`es and C\^ome Bissuel and Olivier Juan and Safia Kedad-Sidhoum
• Abstract要約: 現実世界のインスタンスのパターンを活用して、与えられた問題に最適化された新しいブランチ戦略をスクラッチから学習します。 本稿では,この課題に特化して設計された新しい強化学習手法であるFMSTSを提案する。
• 参考スコア（独自算出の注目度）: 0.10499611180329801
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Mixed integer linear programs are commonly solved by Branch and Bound algorithms. A key factor of the efficiency of the most successful commercial solvers is their fine-tuned heuristics. In this paper, we leverage patterns in real-world instances to learn from scratch a new branching strategy optimised for a given problem and compare it with a commercial solver. We propose FMSTS, a novel Reinforcement Learning approach specifically designed for this task. The strength of our method lies in the consistency between a local value function and a global metric of interest. In addition, we provide insights for adapting known RL techniques to the Branch and Bound setting, and present a new neural network architecture inspired from the literature. To our knowledge, it is the first time Reinforcement Learning has been used to fully optimise the branching strategy. Computational experiments show that our method is appropriate and able to generalise well to new instances.
• Abstract（参考訳）: 混合整数線形プログラムは分岐および境界アルゴリズムによって一般に解かれる。 最も成功した商用問題解決者の効率の重要な要素は、細調整されたヒューリスティックスである。 本稿では,実世界のインスタンスのパターンを活用して,与えられた問題に対して最適化された新たな分岐戦略をスクラッチから学習し,それを商用解法と比較する。 本稿では,この課題に特化して設計された新しい強化学習手法FMSTSを提案する。 本手法の強みは,局所値関数と大域的関心度との整合性にある。 さらに、既知のRLテクニックをブランチとバウンド設定に適用するための洞察を提供し、文献から着想を得た新しいニューラルネットワークアーキテクチャを提案する。 私たちの知る限り、分岐戦略を完全に最適化するために強化学習が使用されたのは初めてです。 計算実験では,提案手法が適切であり,新しいインスタンスにうまく一般化できることを示す。

関連論文リスト

• Hierarchically Structured Task-Agnostic Continual Learning [0.0]
  本研究では,連続学習のタスク非依存的な視点を取り入れ,階層的情報理論の最適性原理を考案する。 我々は,情報処理経路の集合を作成することで,忘れを緩和する,Mixture-of-Variational-Experts層と呼ばれるニューラルネットワーク層を提案する。 既存の連続学習アルゴリズムのようにタスク固有の知識を必要としない。
  論文  参考訳（メタデータ） (2022-11-14T19:53:15Z)
• Deep Reinforcement Learning for Exact Combinatorial Optimization: Learning to Branch [13.024115985194932]
  本稿では、強化学習(RL)パラダイムを用いた最適化において、データラベリングと推論の問題を解決するための新しいアプローチを提案する。 我々は模倣学習を用いてRLエージェントをブートストラップし、PPO(Proximal Policy)を使用してグローバルな最適なアクションを探索する。
  論文  参考訳（メタデータ） (2022-06-14T16:35:58Z)
• Reinforcement Learning for Branch-and-Bound Optimisation using Retrospective Trajectories [72.15369769265398]
  機械学習は分岐のための有望なパラダイムとして登場した。 分岐のための単純かつ効果的なRLアプローチであるレトロ分岐を提案する。 我々は現在最先端のRL分岐アルゴリズムを3～5倍に上回り、500の制約と1000の変数を持つMILP上での最高のILメソッドの性能の20%以内である。
  論文  参考訳（メタデータ） (2022-05-28T06:08:07Z)
• Evolving Reinforcement Learning Algorithms [186.62294652057062]
  メタラーニング強化学習アルゴリズムの手法を提案する。 学習アルゴリズムはドメインに依存しないため、トレーニング中に見えない新しい環境に一般化することができる。 従来の制御タスク、gridworld型タスク、atariゲームよりも優れた一般化性能を得る2つの学習アルゴリズムに注目した。
  論文  参考訳（メタデータ） (2021-01-08T18:55:07Z)
• Fast Few-Shot Classification by Few-Iteration Meta-Learning [173.32497326674775]
  数ショット分類のための高速な最適化に基づくメタラーニング手法を提案する。 我々の戦略はメタ学習において学習すべき基礎学習者の目的の重要な側面を可能にする。 我々は、我々のアプローチの速度と効果を実証し、総合的な実験分析を行う。
  論文  参考訳（メタデータ） (2020-10-01T15:59:31Z)
• Discovering Reinforcement Learning Algorithms [53.72358280495428]
  強化学習アルゴリズムは、いくつかのルールの1つに従ってエージェントのパラメータを更新する。 本稿では,更新ルール全体を検出するメタラーニング手法を提案する。 これには、一連の環境と対話することで、"何を予測するか"(例えば、値関数)と"どのように学習するか"の両方が含まれている。
  論文  参考訳（メタデータ） (2020-07-17T07:38:39Z)
• Meta-learning with Stochastic Linear Bandits [120.43000970418939]
  我々は、よく知られたOFULアルゴリズムの正規化バージョンを実装するバンディットアルゴリズムのクラスを考える。 我々は,タスク数の増加とタスク分散の分散が小さくなると,タスクを個別に学習する上で,我々の戦略が大きな優位性を持つことを理論的および実験的に示す。
  論文  参考訳（メタデータ） (2020-05-18T08:41:39Z)
• Unbiased Deep Reinforcement Learning: A General Training Framework for Existing and Future Algorithms [3.7050607140679026]
  本稿では、概念的に理解可能で、強化学習のための全ての実行可能なアルゴリズムに一般化し易い、新しいトレーニングフレームワークを提案する。 我々はモンテカルロサンプリングを用いて生のデータ入力を実現し、マルコフ決定プロセスシーケンスを達成するためにバッチでそれらを訓練する。 我々は、典型的な離散的かつ連続的なシナリオを扱うために、新しいフレームワークに埋め込まれたアルゴリズムをいくつか提案する。
  論文  参考訳（メタデータ） (2020-05-12T01:51:08Z)
• A General Large Neighborhood Search Framework for Solving Integer Linear Programs [46.62993477453986]
  我々は整数プログラムの解法に重点を置いており、我々のアプローチは大規模近傍探索(SLN)パラダイムに根ざしている。 我々のLSSフレームワークは、Gurobiのような最先端の商用解法と比較して、大幅に性能が向上することを示した。
  論文  参考訳（メタデータ） (2020-03-29T23:08:14Z)
• Model-based Multi-Agent Reinforcement Learning with Cooperative Prioritized Sweeping [4.5497948012757865]
  本稿では,新しいモデルに基づく強化学習アルゴリズム,Cooperative Prioritized Sweepingを提案する。 このアルゴリズムは、値関数を近似するために因子化を利用することにより、大きな問題に対するサンプル効率の学習を可能にする。 我々の手法は、よく知られたSysAdminベンチマークとランダム化環境の両方において、最先端の協調的なQ-ラーニングアルゴリズムよりも優れている。
  論文  参考訳（メタデータ） (2020-01-15T19:13:44Z)

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

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