論文の概要: A Deep Reinforcement Learning Framework For Column Generation
- arxiv url: http://arxiv.org/abs/2206.02568v1
- Date: Fri, 3 Jun 2022 03:58:54 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-12 19:19:26.482753
- Title: A Deep Reinforcement Learning Framework For Column Generation
- Title（参考訳）: 列生成のための深層強化学習フレームワーク
- Authors: Cheng Chi, Amine Mohamed Aboussalah, Elias B. Khalil, Juyoung Wang,
Zoha Sherkat-Masoumi
- Abstract要約: カラム生成(CG)は、非常に多数の変数(カラム)を持つ線形プログラムを解くための反復アルゴリズムである。
CGのための最初の強化学習(RL)手法であるRCCGを提案する。
各繰り返しの局所情報に基づいて列をミオプティックに選択する典型的な列選択規則とは異なり、CGを逐次決定問題として扱う。
- 参考スコア（独自算出の注目度）: 13.767526395378638
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Column Generation (CG) is an iterative algorithm for solving linear programs
(LPs) with an extremely large number of variables (columns). CG is the
workhorse for tackling large-scale integer linear programs, which rely on CG to
solve LP relaxations within a branch and bound algorithm. Two canonical
applications are the Cutting Stock Problem (CSP) and Vehicle Routing Problem
with Time Windows (VRPTW). In VRPTW, for example, each binary variable
represents the decision to include or exclude a route, of which there are
exponentially many; CG incrementally grows the subset of columns being used,
ultimately converging to an optimal solution. We propose RLCG, the first
Reinforcement Learning (RL) approach for CG. Unlike typical column selection
rules which myopically select a column based on local information at each
iteration, we treat CG as a sequential decision-making problem, as the column
selected in an iteration affects subsequent iterations of the algorithm. This
perspective lends itself to a Deep Reinforcement Learning approach that uses
Graph Neural Networks (GNNs) to represent the variable-constraint structure in
the LP of interest. We perform an extensive set of experiments using the
publicly available BPPLIB benchmark for CSP and Solomon benchmark for VRPTW.
RLCG converges faster and reduces the number of CG iterations by 22.4% for CSP
and 40.9% for VRPTW on average compared to a commonly used greedy policy.
- Abstract（参考訳）: カラム生成(CG)は、非常に多数の変数(カラム)を持つ線形プログラム(LP)を解くための反復アルゴリズムである。
CGは、分岐および有界アルゴリズム内のLP緩和を解決するためにCGに依存する大規模な整数線形プログラムを扱うための作業場である。
CSP(Cutting Stock Problem)とVRPTW(Vine Routing Problem with Time Windows)の2つの標準的な応用例がある。
例えば、VRPTWでは、各バイナリ変数は、指数関数的に多くの経路を包含または除外する決定を表し、CGは使われる列のサブセットを徐々に増加させ、最終的には最適解に収束する。
CGのための最初の強化学習(RL)手法であるRCCGを提案する。
各繰り返しの局所情報に基づいて列をミオプティックに選択する典型的な列選択ルールとは異なり、反復で選択した列がアルゴリズムのその後の反復に影響を与えるため、CGを逐次決定問題として扱う。
この観点は、関心のLPにおける可変制約構造を表現するためにグラフニューラルネットワーク(GNN)を使用するDeep Reinforcement Learningアプローチにつながります。
我々は、CSP用のBPPLIBベンチマークとVRPTW用のSolomonベンチマークを用いて、幅広い実験を行う。
RLCGはより早く収束し、CSPは22.4%、VRPTWは40.9%削減される。
関連論文リスト
- Learn2Aggregate: Supervised Generation of Chvátal-Gomory Cuts Using Graph Neural Networks [24.126826148945586]
混合整数線形プログラミング(MILP)におけるChv'atal-Gomory(CG)カットの生成を最適化するための機械学習フレームワークを提案する。
このフレームワークは、CGカット生成におけるアグリゲーションに有用な制約を分類するために、グラフニューラルネットワークを訓練する。
本手法は,標準CG法と同程度の積分性ギャップを約$textittwice$で埋めると同時に,40$%高速に動作させる。
論文 参考訳（メタデータ） (2024-09-10T14:41:46Z) - A Reinforcement-Learning-Based Multiple-Column Selection Strategy for
Column Generation [33.03891490706789]
列生成は大規模線形プログラミング問題の解決において最も成功した手法の1つである。
本稿では, 強化学習に基づく複数カラム選択戦略を提案する。
本手法は,カットストック問題とグラフカラー化問題という2つの問題に対して評価する。
論文 参考訳（メタデータ） (2023-12-21T11:35:10Z) - Solving a Class of Cut-Generating Linear Programs via Machine Learning [0.0]
カット生成線形プログラム(CGLP)は分離オラクルとして重要な役割を担い、混合整数プログラムの可能な領域に対して有効な不等式を生成する。
分岐木と分岐木のノードでデュアルPを実行するのは、ノード候補の数と、ノードが有用な切断平面を許容する事前知識がないため、計算的に煩雑である。
本稿では,分岐木ノードで切断面を生成できるかどうかを判定する,マシンPクラスの最適値を近似する学習に基づく新しいフレームワークを提案する。
論文 参考訳（メタデータ） (2023-10-30T18:31:52Z) - Enhancing Column Generation by Reinforcement Learning-Based
Hyper-Heuristic for Vehicle Routing and Scheduling Problems [9.203492057735074]
カラム生成(CG)は変数を動的に生成することで大規模問題を解決する重要な手法である。
CGの性能を高めるために,RLHHと呼ばれる強化学習に基づく超ヒューリスティックフレームワークを提案する。
論文 参考訳（メタデータ） (2023-10-15T00:05:50Z) - Learning To Dive In Branch And Bound [95.13209326119153]
グラフニューラルネットワークを用いて特定の潜水構造を学習するためのL2Diveを提案する。
我々は、変数の割り当てを予測するために生成モデルを訓練し、線形プログラムの双対性を利用して潜水決定を行う。
論文 参考訳（メタデータ） (2023-01-24T12:01:45Z) - General Cutting Planes for Bound-Propagation-Based Neural Network
Verification [144.7290035694459]
任意の切削平面制約を加えることができるような境界伝搬手順を一般化する。
MIPソルバは、境界プロパゲーションベースの検証器を強化するために高品質な切削面を生成することができる。
本手法は,oval20ベンチマークを完全解き,oval21ベンチマークの2倍のインスタンスを検証できる最初の検証器である。
論文 参考訳（メタデータ） (2022-08-11T10:31:28Z) - Enhancing Column Generation by a Machine-Learning-Based Pricing
Heuristic for Graph Coloring [5.278929511653199]
カラム生成(CG)は,大規模最適化問題の解決に有効な手法である。
本稿では,高品質な列を効率的に生成できる機械学習価格ヒューリスティックを提案する。
論文 参考訳（メタデータ） (2021-12-08T03:58:25Z) - Breaking the Linear Iteration Cost Barrier for Some Well-known
Conditional Gradient Methods Using MaxIP Data-structures [49.73889315176884]
条件勾配法(CGM)は現代の機械学習で広く使われている。
ほとんどの取り組みは、全体の実行時間を短縮する手段として、イテレーションの数を減らすことに重点を置いています。
本稿では,多くの基本最適化アルゴリズムに対して,イテレーション毎のコストがパラメータ数にサブ線形である最初のアルゴリズムを示す。
論文 参考訳（メタデータ） (2021-11-30T05:40:14Z) - COPS: Controlled Pruning Before Training Starts [68.8204255655161]
最先端のディープニューラルネットワーク(DNN)プルーニング技術は、トレーニング開始前にワンショットで適用され、プルーニングスコアと呼ばれる単一の基準の助けを借りてスパースアーキテクチャを評価する。
この作業では、単一プルーニング基準に集中するのではなく、任意のGASを組み合わせてより強力なプルーニング戦略を構築するためのフレームワークを提供します。
論文 参考訳（メタデータ） (2021-07-27T08:48:01Z) - Gradient Coding with Dynamic Clustering for Straggler-Tolerant
Distributed Learning [55.052517095437]
勾配降下(GD)は、複数の労働者にデータセットを分散することで学習タスクの並列化に広く用いられている。
分散同期gdにおけるイテレーション完了時間ごとの重要なパフォーマンスボトルネックは$straggling$ workersである。
コード化された分散技術は、最近ストラグラーを緩和し、労働者に冗長な計算を割り当てることでgdイテレーションを高速化するために導入された。
本稿では,従来のトラグリング動作に依存する可能性のあるコードの中から,冗長なデータを労働者に割り当てて選択する動的GC方式を提案する。
論文 参考訳（メタデータ） (2021-03-01T18:51:29Z) - Improved Algorithms for Conservative Exploration in Bandits [113.55554483194832]
文脈線形帯域設定における保守的学習問題について検討し、新しいアルゴリズムである保守的制約付きLinUCB(CLUCB2)を導入する。
我々は、既存の結果と一致したCLUCB2に対する後悔の限界を導き、多くの合成および実世界の問題において、最先端の保守的バンディットアルゴリズムよりも優れていることを実証的に示す。
論文 参考訳（メタデータ） (2020-02-08T19:35:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。