Fugu-MT 論文翻訳(概要): Differentiable Combinatorial Scheduling at Scale

論文の概要: Differentiable Combinatorial Scheduling at Scale

arxiv url: http://arxiv.org/abs/2406.06593v1
Date: Thu, 6 Jun 2024 02:09:39 GMT
ステータス: 処理完了
システム内更新日: 2024-06-12 21:14:20.631660
Title: Differentiable Combinatorial Scheduling at Scale
Title（参考訳）: スケールでの差別化可能なコンビニアルスケジューリング
Authors: Mingju Liu, Yingjie Li, Jiaqi Yin, Zhiru Zhang, Cunxi Yu,
Abstract要約: 本稿では,Gumbel-Softmax微分可能なサンプリング手法を用いて,微分可能なスケジューリングフレームワークを提案する。スケジューリングタスクの不等式制約をエンコードするために,任意の不等式制約を積極的にエンコードするテキスト制約付きGumbel Trickを導入する。本手法は, トレーニングデータを必要とせずに, 勾配降下による効率よく, スケーラブルなスケジューリングを容易にする。
参考スコア（独自算出の注目度）: 18.09256072039255
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: This paper addresses the complex issue of resource-constrained scheduling, an NP-hard problem that spans critical areas including chip design and high-performance computing. Traditional scheduling methods often stumble over scalability and applicability challenges. We propose a novel approach using a differentiable combinatorial scheduling framework, utilizing Gumbel-Softmax differentiable sampling technique. This new technical allows for a fully differentiable formulation of linear programming (LP) based scheduling, extending its application to a broader range of LP formulations. To encode inequality constraints for scheduling tasks, we introduce \textit{constrained Gumbel Trick}, which adeptly encodes arbitrary inequality constraints. Consequently, our method facilitates an efficient and scalable scheduling via gradient descent without the need for training data. Comparative evaluations on both synthetic and real-world benchmarks highlight our capability to significantly improve the optimization efficiency of scheduling, surpassing state-of-the-art solutions offered by commercial and open-source solvers such as CPLEX, Gurobi, and CP-SAT in the majority of the designs.
Abstract（参考訳）: 本稿では、チップ設計や高性能コンピューティングを含む重要な領域にまたがるNPハード問題である資源制約スケジューリングの複雑な問題に対処する。従来のスケジューリング手法は、スケーラビリティと適用性の問題に悩まされることが多い。本稿では,Gumbel-Softmax微分可能なサンプリング手法を用いて,微分可能な組合せスケジューリングフレームワークを用いた新しい手法を提案する。この新しい技術は、線形プログラミング(LP)ベースのスケジューリングを完全に微分可能な定式化を可能にし、その適用範囲を幅広いLP定式化にまで広げる。スケジューリングタスクの不等式制約をエンコードするために、任意の不等式制約を積極的にエンコードする \textit{constrained Gumbel Trick} を導入する。そこで本手法は, 学習データを必要とせずに, 勾配降下による効率的な, スケーラブルなスケジューリングを容易にする。 CPLEX, Gurobi, CP-SATといった商用およびオープンソースソルバが提供する最先端のソリューションを大半を越え, スケジューリングの最適化効率を大幅に向上させる能力について, 実世界のベンチマークと実世界のベンチマークを比較した。

関連論文リスト

Optimization-Driven Adaptive Experimentation [7.948144726705323]
実世界の実験には、バッチで遅延したフィードバック、非定常性、複数の目的と制約、そして(時には)パーソナライゼーションが含まれる。これらの課題にプロブレム単位で対処するための適応的手法の調整は不可能であり、静的設計はデファクトスタンダードのままである。本稿では,多種多様な目的,制約,統計的手順を柔軟に組み込む数学的プログラミングの定式化について述べる。
論文参考訳（メタデータ） (2024-08-08T16:29:09Z)
A Penalty-Based Guardrail Algorithm for Non-Decreasing Optimization with Inequality Constraints [1.5498250598583487]
伝統的な数学的プログラミングの解法は制約付き最小化問題を解くのに長い計算時間を必要とする。ペナルティに基づくガードレールアルゴリズム(PGA)を提案する。
論文参考訳（メタデータ） (2024-05-03T10:37:34Z)
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)
Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNets [86.43523688236077]
組合せ最適化(CO)問題はしばしばNPハードであり、正確なアルゴリズムには及ばない。 GFlowNetsは、複合非正規化密度を逐次サンプリングする強力な機械として登場した。本稿では,異なる問題に対してマルコフ決定プロセス(MDP)を設計し,条件付きGFlowNetを学習して解空間からサンプルを作成することを提案する。
論文参考訳（メタデータ） (2023-05-26T15:13:09Z)
A Hierarchical Temporal Planning-Based Approach for Dynamic Hoist Scheduling Problems [11.66506213335498]
ホイストスケジューリングは、自律デバイスの開発で産業応用の電気めっきのボトルネックとなっている。適応型PDDLの形で新しい時間計画問題としてホイストスケジューリング問題を定式化する。この問題に対するソリューションメソッドの評価に使用できる実生活ベンチマークインスタンスのコレクションを提供する。
論文参考訳（メタデータ） (2022-12-11T05:30:44Z)
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)
A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs [91.07247251502564]
本稿では,2つの世界の長所を結合するハイブリッドな手法を提案する。この手法では,グラフを最適化する上層学習手法とバイレベルフレームワークを開発する。このような二段階のアプローチは、元のハードCOでの学習を単純化し、モデルキャパシティの需要を効果的に軽減することができる。
論文参考訳（メタデータ） (2021-06-09T09:18:18Z)
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)
Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
論文参考訳（メタデータ） (2020-07-07T21:26:35Z)

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

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