論文の概要: Learning Large Neighborhood Search Policy for Integer Programming

• arxiv url: http://arxiv.org/abs/2111.03466v1
• Date: Mon, 1 Nov 2021 09:10:49 GMT
• ステータス: 処理完了
• システム内更新日: 2021-11-14 15:12:53.346516
• Title: Learning Large Neighborhood Search Policy for Integer Programming
• Title（参考訳）: 整数計画のための大近所探索ポリシーの学習
• Authors: Yaoxin Wu, Wen Song, Zhiguang Cao and Jie Zhang
• Abstract要約: 整数プログラミング (IP) のための大規模近傍探索 (LNS) ポリシーを学習するための深層強化学習 (RL) 手法を提案する。 各変数のバイナリ決定に分解することで、すべてのサブセットを表現します。 次に、ニューラルネットワークを設計し、各変数のポリシーを並列に学習し、カスタマイズされたアクター批判アルゴリズムでトレーニングする。
• 参考スコア（独自算出の注目度）: 14.089039170072084
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose a deep reinforcement learning (RL) method to learn large neighborhood search (LNS) policy for integer programming (IP). The RL policy is trained as the destroy operator to select a subset of variables at each step, which is reoptimized by an IP solver as the repair operator. However, the combinatorial number of variable subsets prevents direct application of typical RL algorithms. To tackle this challenge, we represent all subsets by factorizing them into binary decisions on each variable. We then design a neural network to learn policies for each variable in parallel, trained by a customized actor-critic algorithm. We evaluate the proposed method on four representative IP problems. Results show that it can find better solutions than SCIP in much less time, and significantly outperform other LNS baselines with the same runtime. Moreover, these advantages notably persist when the policies generalize to larger problems. Further experiments with Gurobi also reveal that our method can outperform this state-of-the-art commercial solver within the same time limit.
• Abstract（参考訳）: 本稿では,整数プログラミング (IP) のための大規模近傍探索 (LNS) ポリシーを学習するための深層強化学習 (RL) 手法を提案する。 RLポリシーはデフォールト演算子として訓練され、各ステップで変数のサブセットを選択し、IPソルバによって修復演算子として再最適化される。 しかし、可変部分集合の組合せ数は典型的なrlアルゴリズムの直接適用を妨げている。 この課題に取り組むために、私たちはすべてのサブセットを各変数のバイナリ決定に分解することで表現します。 次に,各変数のポリシを並列に学習するためにニューラルネットワークを設計,カスタマイズされたアクタ-クリティックアルゴリズムでトレーニングする。 提案手法を4つの代表的IP問題に対して評価する。 結果は、SCIPよりもはるかに少ない時間でより良いソリューションを見つけることができ、同じランタイムで他のLSSベースラインよりも大幅に優れていることを示している。 さらに、これらの利点は、ポリシーがより大きな問題に一般化するときに特に持続する。 また、gurobiによるさらなる実験により、この最先端の商用解法を同じ時間内に実現できることが判明した。

関連論文リスト

• Offline Imitation Learning from Multiple Baselines with Applications to Compiler Optimization [17.729842629392742]
  我々は,Kベースラインポリシーで収集した一連のトラジェクトリを与えられる強化学習問題について検討する。 目標は、状態空間全体におけるベースラインの最高の組み合わせと同様に、機能するポリシーを学ぶことです。
  論文  参考訳（メタデータ） (2024-03-28T14:34:02Z)
• Jump-Start Reinforcement Learning [68.82380421479675]
  本稿では、オフラインデータやデモ、あるいは既存のポリシーを使ってRLポリシーを初期化するメタアルゴリズムを提案する。 特に,タスク解決に2つのポリシーを利用するアルゴリズムであるJump-Start Reinforcement Learning (JSRL)を提案する。 実験により、JSRLは既存の模倣と強化学習アルゴリズムを大幅に上回っていることを示す。
  論文  参考訳（メタデータ） (2022-04-05T17:25:22Z)
• An actor-critic algorithm with policy gradients to solve the job shop scheduling problem using deep double recurrent agents [1.3812010983144802]
  ジョブショップスケジューリング問題(JSSP)に対する深層強化学習手法を提案する。 目的は、ジョブやマシンの数によって異なるJSSPインスタンスのディストリビューションについて学べるgreedyのようなものを構築することである。 予想通り、モデルはある程度は、トレーニングで使用されるものと異なる分布から生じるより大きな問題やインスタンスに一般化することができる。
  論文  参考訳（メタデータ） (2021-10-18T07:55:39Z)
• Direct Random Search for Fine Tuning of Deep Reinforcement Learning Policies [5.543220407902113]
  直接ランダム検索は、決定論的ロールアウトを用いて直接最適化することにより、DRLポリシーを微調整するのに非常に効果的であることを示す。 その結果, 本手法は, テストした環境において, より一貫性があり, 高性能なエージェントが得られることがわかった。
  論文  参考訳（メタデータ） (2021-09-12T20:12:46Z)
• Online Sub-Sampling for Reinforcement Learning with General Function Approximation [111.01990889581243]
  本稿では,RLアルゴリズムによって収集されたデータポイントの情報取得量を測定する,効率的なオンラインサブサンプリングフレームワークを確立する。 複雑性バウンド関数クラスを持つ値ベースのメソッドの場合、$proptooperatornamepolylog(K)$ timesに対してのみポリシーを更新する必要がある。 少なくとも$Omega(K)$倍のポリシーを更新する既存のアプローチとは対照的に、当社のアプローチはポリシーの解決における最適化コールの数を劇的に削減します。
  論文  参考訳（メタデータ） (2021-06-14T07:36:25Z)
• Discovering a set of policies for the worst case reward [15.682107694476779]
  我々は、SIPs、set-max Policy(SMPs)の最も保守的なインスタンス化に焦点を当てる。 我々の主な貢献は、タスクセットにおける結果のSMPの最悪のパフォーマンスを最大化するためにポリシーセットを構築するポリシー反復アルゴリズムである。 結果,SMPの最悪の性能は各イテレーションで厳格に向上し,性能改善につながるポリシーが存在しない場合にのみアルゴリズムが停止することを示す。
  論文  参考訳（メタデータ） (2021-02-08T16:27:09Z)
• Evolving Reinforcement Learning Algorithms [186.62294652057062]
  メタラーニング強化学習アルゴリズムの手法を提案する。 学習アルゴリズムはドメインに依存しないため、トレーニング中に見えない新しい環境に一般化することができる。 従来の制御タスク、gridworld型タスク、atariゲームよりも優れた一般化性能を得る2つの学習アルゴリズムに注目した。
  論文  参考訳（メタデータ） (2021-01-08T18:55:07Z)
• Solving Mixed Integer Programs Using Neural Networks [57.683491412480635]
  本稿では,mipソルバの2つのキーサブタスクに学習を適用し,高品質なジョイント変数割当を生成し,その割当と最適課題との客観的値の差を限定する。 提案手法は,ニューラルネットワークに基づく2つのコンポーネントであるニューラルダイバーディングとニューラルブランチを構築し,SCIPなどのベースMIPソルバで使用する。 2つのGoogle生産データセットとMIPLIBを含む6つの現実世界データセットに対するアプローチを評価し、それぞれに別々のニューラルネットワークをトレーニングする。
  論文  参考訳（メタデータ） (2020-12-23T09:33:11Z)
• Discovering Reinforcement Learning Algorithms [53.72358280495428]
  強化学習アルゴリズムは、いくつかのルールの1つに従ってエージェントのパラメータを更新する。 本稿では,更新ルール全体を検出するメタラーニング手法を提案する。 これには、一連の環境と対話することで、"何を予測するか"(例えば、値関数)と"どのように学習するか"の両方が含まれている。
  論文  参考訳（メタデータ） (2020-07-17T07:38:39Z)
• Reinforcement Learning for Variable Selection in a Branch and Bound Algorithm [0.10499611180329801]
  現実世界のインスタンスのパターンを活用して、与えられた問題に最適化された新しいブランチ戦略をスクラッチから学習します。 本稿では,この課題に特化して設計された新しい強化学習手法であるFMSTSを提案する。
  論文  参考訳（メタデータ） (2020-05-20T13:15:48Z)
• Learning Adaptive Exploration Strategies in Dynamic Environments Through Informed Policy Regularization [100.72335252255989]
  本研究では,動的環境に効果的に適応する探索探索探索戦略の課題について検討する。 本稿では,各タスクにおける報酬を最大化するために訓練された情報ポリシを用いて,RNNベースのポリシーのトレーニングを規則化する新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-05-06T16:14:48Z)

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

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