論文の概要: Accelerate Presolve in Large-Scale Linear Programming via Reinforcement Learning

• arxiv url: http://arxiv.org/abs/2310.11845v1
• Date: Wed, 18 Oct 2023 09:51:59 GMT
• ステータス: 処理完了
• システム内更新日: 2023-10-19 17:08:28.307021
• Title: Accelerate Presolve in Large-Scale Linear Programming via Reinforcement Learning
• Title（参考訳）: 強化学習による大規模線形プログラミングの高速化
• Authors: Yufei Kuang, Xijun Li, Jie Wang, Fangzhou Zhu, Meng Lu, Zhihai Wang, Jia Zeng, Houqiang Li, Yongdong Zhang, Feng Wu
• Abstract要約: 本稿では,P1)-(P3) を同時に扱うための簡易かつ効率的な強化学習フレームワーク,すなわち,事前解決のための強化学習(RL4Presolve)を提案する。 2つの解法と8つのベンチマーク(実世界と合成)の実験により、RL4Presolveは大規模LPの解法効率を大幅に改善することを示した。
• 参考スコア（独自算出の注目度）: 92.31528918811007
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Large-scale LP problems from industry usually contain much redundancy that severely hurts the efficiency and reliability of solving LPs, making presolve (i.e., the problem simplification module) one of the most critical components in modern LP solvers. However, how to design high-quality presolve routines -- that is, the program determining (P1) which presolvers to select, (P2) in what order to execute, and (P3) when to stop -- remains a highly challenging task due to the extensive requirements on expert knowledge and the large search space. Due to the sequential decision property of the task and the lack of expert demonstrations, we propose a simple and efficient reinforcement learning (RL) framework -- namely, reinforcement learning for presolve (RL4Presolve) -- to tackle (P1)-(P3) simultaneously. Specifically, we formulate the routine design task as a Markov decision process and propose an RL framework with adaptive action sequences to generate high-quality presolve routines efficiently. Note that adaptive action sequences help learn complex behaviors efficiently and adapt to various benchmarks. Experiments on two solvers (open-source and commercial) and eight benchmarks (real-world and synthetic) demonstrate that RL4Presolve significantly and consistently improves the efficiency of solving large-scale LPs, especially on benchmarks from industry. Furthermore, we optimize the hard-coded presolve routines in LP solvers by extracting rules from learned policies for simple and efficient deployment to Huawei's supply chain. The results show encouraging economic and academic potential for incorporating machine learning to modern solvers.
• Abstract（参考訳）: 産業からの大規模lp問題には、通常多くの冗長性が含まれており、lp解決の効率と信頼性が著しく損なわれ、プリソルバ(すなわち問題単純化モジュール)は現代のlpソルバにおいて最も重要なコンポーネントの1つとなっている。 However, how to design high-quality presolve routines -that is, the program determining (P1) which presolvers to select, (P2) in what order to execute, and (P3) when to stop -- remains a highly challenging task due to the extensive requirements on expert knowledge and the large search space. Due to the sequential decision property of the task and the lack of expert demonstrations, we propose a simple and efficient reinforcement learning (RL) framework -- namely, reinforcement learning for presolve (RL4Presolve) -to tackle (P1)-(P3) simultaneously. 具体的には、ルーチン設計タスクをマルコフ決定プロセスとして定式化し、高品質のプリソルバルーチンを効率的に生成するための適応的なアクションシーケンスを持つrlフレームワークを提案する。 適応的なアクションシーケンスは複雑な振る舞いを効率的に学習し、様々なベンチマークに適応するのに役立ちます。 2つの解法(オープンソースと商用)と8つのベンチマーク(実世界と合成)の実験により、RL4Presolveは大規模LP、特に業界からのベンチマークの解決効率を大幅に改善することを示した。 さらに,Huaweiのサプライチェーンへのシンプルかつ効率的な展開のための学習ポリシからルールを抽出することにより,LPソルバのハードコード事前解決ルーチンを最適化する。 その結果,現代の問題解決者に機械学習を組み込むための経済的,学術的な可能性を示唆した。

関連論文リスト

• Enhancing Multi-Step Reasoning Abilities of Language Models through Direct Q-Function Optimization [50.485788083202124]
  強化学習(Reinforcement Learning, RL)は、大規模言語モデルを人間の好みと整合させ、複雑なタスクを遂行する能力を向上させる上で重要な役割を担っている。 反応生成過程をマルコフ決定プロセス(MDP)として定式化し,ソフトアクター・クリティック(SAC)フレームワークを用いて,言語モデルによって直接パラメータ化されたQ関数を最適化する,直接Q関数最適化(DQO)を提案する。 GSM8KとMATHという2つの数学問題解決データセットの実験結果から、DQOは従来の手法よりも優れており、言語モデルを整合させるための有望なオフライン強化学習手法として確立されている。
  論文  参考訳（メタデータ） (2024-10-11T23:29:20Z)
• PEAR: Primitive enabled Adaptive Relabeling for boosting Hierarchical Reinforcement Learning [25.84621883831624]
  階層的強化学習は、時間的抽象と探索の増大を利用して複雑な長い水平方向のタスクを解く可能性がある。 プリミティブ・アダプティブ・アダプティブ・レバーベリング(PEAR)を提案する。 まず,いくつかの専門家による実験を適応的に実施し,効率的なサブゴール管理を実現する。 次に、強化学習(RL)と模倣学習(IL)を併用してHRLエージェントを共同最適化する。
  論文  参考訳（メタデータ） (2023-06-10T09:41:30Z)
• Flexible Job Shop Scheduling via Dual Attention Network Based Reinforcement Learning [73.19312285906891]
  フレキシブルなジョブショップスケジューリング問題(FJSP)では、複数のマシンで操作を処理でき、操作とマシンの間の複雑な関係が生じる。 近年, 深層強化学習(DRL)を用いて, FJSP解決のための優先派遣規則(PDR)を学習している。 本稿では,Deep機能抽出のための自己注意モデルと,スケーラブルな意思決定のためのDRLの利点を生かした,エンドツーエンド学習フレームワークを提案する。
  論文  参考訳（メタデータ） (2023-05-09T01:35:48Z)
• Deep reinforcement learning applied to an assembly sequence planning problem with user preferences [1.0558951653323283]
  本稿では,アセンブリシーケンス計画問題におけるDRL手法の実装に対するアプローチを提案する。 提案手法では,RL環境のパラメトリックな動作を導入し,トレーニング時間とサンプル効率を改善する。 その結果,人的相互作用を伴う組立シーケンス計画問題への深層強化学習の適用の可能性が示唆された。
  論文  参考訳（メタデータ） (2023-04-13T14:25:15Z)
• Learning to Optimize for Reinforcement Learning [58.01132862590378]
  強化学習(Reinforcement Learning, RL)は、教師付き学習とは本質的に異なり、実際、これらの学習は単純なRLタスクでもうまく機能しない。 エージェント勾配分布は非独立で同一分布であり、非効率なメタトレーニングをもたらす。 おもちゃのタスクでしか訓練されていないが、我々の学習はブラックスの目に見えない複雑なタスクを一般化できることを示した。
  論文  参考訳（メタデータ） (2023-02-03T00:11:02Z)
• Learning to Optimize Permutation Flow Shop Scheduling via Graph-based Imitation Learning [70.65666982566655]
  置換フローショップスケジューリング(PFSS)は製造業で広く使われている。 我々は,より安定かつ正確に収束を加速する専門家主導の模倣学習を通じてモデルを訓練することを提案する。 我々のモデルのネットワークパラメータはわずか37%に減少し、エキスパートソリューションに対する我々のモデルの解のギャップは平均6.8%から1.3%に減少する。
  論文  参考訳（メタデータ） (2022-10-31T09:46:26Z)
• Learning Algorithms for Intelligent Agents and Mechanisms [4.251500966181852]
  本稿では,2つの異なる文脈における最適意思決定のための学習アルゴリズム,パート1における強化学習,パート2におけるオークションデザインについて検討する。 第2章では統計物理学に触発された強化学習(Reinforcement Learning, RL)の新たなアプローチを開発し, 最適化された望ましい特性を持つ最適ポリシを学習するだけでなく, 最大エントロピーRLに新たな光を照射する。 第3章では、ベイズ的視点を用いてRLの一般化問題に取り組み、環境の不完全な知識が完全に観測されたマルコフ決定過程(MDP)を部分的に観測されたMDP(POMD)に変換することを効果的に示している。
  論文  参考訳（メタデータ） (2022-10-06T03:12:43Z)
• Math Programming based Reinforcement Learning for Multi-Echelon Inventory Management [1.9161790404101895]
  強化学習は、ロボット工学、ゲーム、その他多くの分野において、かなりのブレークスルーをもたらしている。 しかし、複雑な実世界の意思決定問題におけるRLの応用は依然として限られている。 これらの特徴は、ステップアクションの問題を解くために列挙法に依存する既存のRL法において、問題を解くのをかなり難しくする。 本研究では,不確実性分布の適切に選択された離散化が,不確実性からのサンプルがごく少ない場合でも,最適なアクターポリシーに近づきうることを示す。 PARLはベースストックを44.7%、RL法を12.1%上回っている。
  論文  参考訳（メタデータ） (2021-12-04T01:40:34Z)
• Safe-Critical Modular Deep Reinforcement Learning with Temporal Logic through Gaussian Processes and Control Barrier Functions [3.5897534810405403]
  強化学習(Reinforcement Learning, RL)は,現実のアプリケーションに対して限られた成功を収める,有望なアプローチである。 本稿では,複数の側面からなる学習型制御フレームワークを提案する。 ECBFをベースとしたモジュラーディープRLアルゴリズムは,ほぼ完全な成功率を達成し,高い確率で安全性を保護することを示す。
  論文  参考訳（メタデータ） (2021-09-07T00:51:12Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)

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

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