論文の概要: NICE: Robust Scheduling through Reinforcement Learning-Guided Integer
Programming
- arxiv url: http://arxiv.org/abs/2109.12171v1
- Date: Fri, 24 Sep 2021 20:16:33 GMT
- ステータス: 処理完了
- システム内更新日: 2021-10-01 09:44:10.152046
- Title: NICE: Robust Scheduling through Reinforcement Learning-Guided Integer
Programming
- Title(参考訳): NICE: 強化学習型整数プログラミングによるロバストスケジューリング
- Authors: Luke Kenworthy, Siddharth Nayak, Christopher Chin and Hamsa
Balakrishnan
- Abstract要約: 我々は,強化学習と整数プログラミングを組み合わせたNICEを提案し,ロバストなスケジューリング問題に対処する。
我々はNICEを用いて、パイロットの飛行スケジュールの割り当てを決定し、破壊の影響を低減する。
実験の結果、NICEは様々なシナリオでスケジュールを作成でき、その結果、ベースラインの定式化よりも33%から48%のディスラプションが減少することがわかった。
- 参考スコア(独自算出の注目度): 5.448283690603358
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Integer programs provide a powerful abstraction for representing a wide range
of real-world scheduling problems. Despite their ability to model general
scheduling problems, solving large-scale integer programs (IP) remains a
computational challenge in practice. The incorporation of more complex
objectives such as robustness to disruptions further exacerbates the
computational challenge. We present NICE (Neural network IP Coefficient
Extraction), a novel technique that combines reinforcement learning and integer
programming to tackle the problem of robust scheduling. More specifically, NICE
uses reinforcement learning to approximately represent complex objectives in an
integer programming formulation. We use NICE to determine assignments of pilots
to a flight crew schedule so as to reduce the impact of disruptions. We compare
NICE with (1) a baseline integer programming formulation that produces a
feasible crew schedule, and (2) a robust integer programming formulation that
explicitly tries to minimize the impact of disruptions. Our experiments show
that, across a variety of scenarios, NICE produces schedules resulting in 33\%
to 48\% fewer disruptions than the baseline formulation. Moreover, in more
severely constrained scheduling scenarios in which the robust integer program
fails to produce a schedule within 90 minutes, NICE is able to build robust
schedules in less than 2 seconds on average.
- Abstract(参考訳): 整数プログラムは、現実世界の幅広いスケジューリング問題を表現するための強力な抽象化を提供する。
一般的なスケジューリング問題をモデル化する能力にもかかわらず、大規模整数プログラム(ip)の解決は計算上の課題である。
破壊に対する堅牢性のようなより複雑な目的の組み入れにより、さらに計算課題が悪化する。
我々は,強化学習と整数プログラミングを組み合わせた新しい手法であるNICE(Neural Network IP Coefficient extract)を提案する。
より具体的には、NICEは整数プログラミングの定式化における複雑な目的を概ね表すために強化学習を使用する。
niceは、飛行クルーのスケジュールに対するパイロットの割り当てを決定し、混乱の影響を減らすために使用します。
我々は,(1)有望なクルースケジュールを生成するベースライン整数計画法と(2)破壊の影響を明示的に最小化しようとする頑健な整数計画法との比較を行った。
私たちの実験では、様々なシナリオでニースがスケジュールを生成し、ベースラインの定式化よりも33-48-%少ないディスラプションとなることを示しています。
さらに、堅牢な整数プログラムが90分以内にスケジュールを作成できなかった、より厳格に制約されたスケジューリングシナリオでは、niceは平均して2秒未満で堅牢なスケジュールを構築することができる。
関連論文リスト
- DNCs Require More Planning Steps [7.837209773889032]
暗黙的アルゴリズム解法の一般化に対する計算時間とメモリの影響について検討する。
計画予算が学習アルゴリズムの挙動を劇的に変える方法を示す。
論文 参考訳(メタデータ) (2024-06-04T10:31:03Z) - A General Framework for Learning from Weak Supervision [93.89870459388185]
本稿では、新しいアルゴリズムを用いて、弱監督(GLWS)から学習するための一般的な枠組みを紹介する。
GLWSの中心は期待最大化(EM)の定式化であり、様々な弱い監督源を順応的に収容している。
また,EM計算要求を大幅に単純化する高度なアルゴリズムを提案する。
論文 参考訳(メタデータ) (2024-02-02T21:48:50Z) - Accelerating Exact Combinatorial Optimization via RL-based
Initialization -- A Case Study in Scheduling [1.3053649021965603]
本研究の目的は、最適化問題に対処する機械学習(ML)を用いた革新的なアプローチを開発することである。
1) 粗粒スケジューラとしての解法, 2) 解緩和, 3) ILPによる正確な解法の3つのステップを含む新しい2段階のRL-to-ILPスケジューリングフレームワークを導入する。
提案フレームワークは, 正確なスケジューリング手法と比較して, 最大128ドルの高速化を実現しつつ, 同一のスケジューリング性能を示す。
論文 参考訳(メタデータ) (2023-08-19T15:52:43Z) - An End-to-End Reinforcement Learning Approach for Job-Shop Scheduling
Problems Based on Constraint Programming [5.070542698701157]
本稿では,CPと強化学習(Reinforcement Learning, RL)を用いてスケジューリング問題を解決する新しいエンドツーエンドアプローチを提案する。
当社のアプローチでは,既存のCPソルバを活用して,プライオリティ・ディスパッチ・ルール(PDR)を学ぶエージェントをトレーニングする。
論文 参考訳(メタデータ) (2023-06-09T08:24:56Z) - RESPECT: Reinforcement Learning based Edge Scheduling on Pipelined Coral
Edge TPUs [12.952987240366781]
本研究は、最適化アルゴリズムの挙動を学習する強化学習(RL)に基づくスケジューリングフレームワークを提案する。
RLは、実行時のオーバーヘッドを短くすることで、ほぼ最適のスケジューリング結果を生成する。
我々のフレームワークは、商用コンパイラ上での実世界のオンチップランタイム推論速度アップを最大$sim2.5times$で実証しています。
論文 参考訳(メタデータ) (2023-04-10T17:22:12Z) - NAPG: Non-Autoregressive Program Generation for Hybrid Tabular-Textual
Question Answering [52.10214317661547]
現在の数値推論法はプログラムシーケンスを自己回帰的にデコードする。
プログラム生成の精度は、デコードステップがエラー伝搬によって展開されるにつれて急激に低下する。
本稿では,非自己回帰型プログラム生成フレームワークを提案する。
論文 参考訳(メタデータ) (2022-11-07T11:25:21Z) - Planning Courses for Student Success at the American College of Greece [0.0]
我々は、ギリシャのアメリカン・カレッジ・オブ・ギリシャの学生が研究を完了するために必要となるコースのスケジュールを最適化する問題をモデル化する。
結果のスケジュールを最適化する目的として,最速の完了時間,コース難易度バランスなど,いくつかの異なる目標を定式化します。
我々は,機械学習とデータマイニングの手法を用いて,受講生が受講生に期待する成績を捉えた。
論文 参考訳(メタデータ) (2022-06-16T10:19:37Z) - Learning from Self-Sampled Correct and Partially-Correct Programs [96.66452896657991]
そこで本研究では,モデルが学習中にサンプリングを行い,自己サンプリングされた完全正当プログラムと部分正当プログラムの両方から学習することを提案する。
自己サンプリング型プログラムと部分修正型プログラムを併用することで,学習とサンプリングプロセスのガイドに役立てることができることを示す。
提案手法は,MLEを用いた単一の参照プログラムからの学習と比較して,パス@kの性能を3.1%から12.3%向上させる。
論文 参考訳(メタデータ) (2022-05-28T03:31:07Z) - A Two-stage Framework and Reinforcement Learning-based Optimization
Algorithms for Complex Scheduling Problems [54.61091936472494]
本稿では、強化学習(RL)と従来の運用研究(OR)アルゴリズムを組み合わせた2段階のフレームワークを開発する。
スケジューリング問題は,有限マルコフ決定過程 (MDP) と混合整数計画過程 (mixed-integer programming process) の2段階で解決される。
その結果,本アルゴリズムは,アジャイルな地球観測衛星スケジューリング問題に対して,安定かつ効率的に十分なスケジューリング計画を得ることができた。
論文 参考訳(メタデータ) (2021-03-10T03:16:12Z) - Combining Deep Learning and Optimization for Security-Constrained
Optimal Power Flow [94.24763814458686]
セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。
SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。
本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
論文 参考訳(メタデータ) (2020-07-14T12:38:21Z) - Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal
Constraints [52.58352707495122]
本稿では,不確実性およびマルチエージェント協調の下での逐次意思決定における重要な計算課題を分離するマルチロボット割当アルゴリズムを提案する。
都市におけるマルチアームコンベヤベルトピック・アンド・プレイスとマルチドローン配送ディスパッチの2つの異なる領域における広範囲なシミュレーション結果について検証を行った。
論文 参考訳(メタデータ) (2020-05-27T01:10:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。