論文の概要: Generalized Conflict-directed Search for Optimal Ordering Problems
- arxiv url: http://arxiv.org/abs/2104.00060v1
- Date: Wed, 31 Mar 2021 18:46:48 GMT
- ステータス: 処理完了
- システム内更新日: 2021-04-02 13:45:08.261821
- Title: Generalized Conflict-directed Search for Optimal Ordering Problems
- Title（参考訳）: 最適順序問題に対する一般化された競合指向探索
- Authors: Jingkai Chen, Yuening Zhang, Cheng Fang, Brian C. Williams
- Abstract要約: 本稿では,イベントの全順序を最適に生成する分枝順序付け法GCDOを提案する。
汎用的な紛争を推論する能力があるため、GCDOは以前の競合指向アプローチCDITOよりも高品質の総注文を見つけるのにはるかに効率的です。
- 参考スコア（独自算出の注目度）: 18.231677739397973
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Solving planning and scheduling problems for multiple tasks with highly
coupled state and temporal constraints is notoriously challenging. An appealing
approach to effectively decouple the problem is to judiciously order the events
such that decisions can be made over sequences of tasks. As many problems
encountered in practice are over-constrained, we must instead find relaxed
solutions in which certain requirements are dropped. This motivates a
formulation of optimality with respect to the costs of relaxing constraints and
the problem of finding an optimal ordering under which this relaxing cost is
minimum. In this paper, we present Generalized Conflict-directed Ordering
(GCDO), a branch-and-bound ordering method that generates an optimal total
order of events by leveraging the generalized conflicts of both inconsistency
and suboptimality from sub-solvers for cost estimation and solution space
pruning. Due to its ability to reason over generalized conflicts, GCDO is much
more efficient in finding high-quality total orders than the previous
conflict-directed approach CDITO. We demonstrate this by benchmarking on
temporal network configuration problems, which involves managing networks over
time and makes necessary tradeoffs between network flows against CDITO and
Mixed Integer-Linear Programing (MILP). Our algorithm is able to solve two
orders of magnitude more benchmark problems to optimality and twice the
problems compared to CDITO and MILP within a runtime limit, respectively.
- Abstract（参考訳）: 高度に結合した状態と時間的制約を持つ複数のタスクの計画とスケジューリングの問題を解決することは、非常に難しい。
問題を効果的に分離するための魅力的なアプローチは、タスクのシーケンス上で決定できるようなイベントを適切に順序づけることである。
実際に遭遇した多くの問題は過剰に制約されているので、ある要求が外れた緩和された解を見つける必要がある。
このことは、制約緩和コストと、この緩和コストが最小となる最適順序を求める問題に対する最適性の定式化を動機付けている。
本稿では,コスト推定と解空間のプルーニングのために,サブソルバから非一貫性と劣最適化の両方の一般化された競合を利用して,イベントの最適総順序を生成する分岐・境界順序法である一般化競合指向順序法(gcdo)を提案する。
一般的なコンフリクトを推論する能力のため、GCDOは以前のコンフリクト指向アプローチCDITOよりも高品質なトータルオーダーを見つけるのにはるかに効率的である。
ネットワークの時間的管理と,CDITOとMILP(Mixed Integer-Linear Programing)とのネットワークフローのトレードオフを含む,時間的ネットワーク構成問題のベンチマークによってこれを実証する。
このアルゴリズムは,実行時限内でcditoとmilpと比較して,最適化のために2桁以上のベンチマーク問題を解くことができる。
関連論文リスト
- Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
本稿では,バッチ取得のための新しいグリーディ型サブセット選択アルゴリズムを提案する。
赤蛍光タンパク質に関する実験により,提案手法は1.69倍少ないクエリでベースライン性能を達成できることが判明した。
論文 参考訳（メタデータ） (2024-06-21T05:57:08Z) - BalMCTS: Balancing Objective Function and Search Nodes in MCTS for
Constraint Optimization Problems [7.196057722218442]
制約問題最適化(COP)は、通常ブランチ・アンド・バウンド(B&B)法によって解決される問題において、複雑な課題を提起する。
COPを解くための深度優先探索アルゴリズムに基づく新しいニューラルネットワークアルゴリズムを提案する。
提案手法は,最初の5つの実現可能な解のうち17.63%未満のギャップを有する実現可能な解を同定する。
論文 参考訳（メタデータ） (2023-12-26T03:09:08Z) - An Efficient Merge Search Matheuristic for Maximising the Net Present
Value of Project Schedules [5.10800491975164]
リソース制約のあるプロジェクトスケジューリングは多くの実用的なアプリケーションにおいて重要な最適化問題である。
本稿では,資源制約のあるプロジェクトスケジューリングを解くために,マージ探索と並列計算に基づく新しい数学ヒューリスティックアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-10-20T13:30:23Z) - Decomposition Strategies and Multi-shot ASP Solving for Job-shop Scheduling [7.977161233209228]
ジョブショップスケジューリング問題(JSP、Job-shop Scheduling Problem)は、ジョブを含むタスクをできるだけ早く完了するように、マシンを共有するタスクをシーケンスに配置する、よく知られた、困難な最適化問題である。
本稿では,ASP(Multi-shot Answer Set Programming)の解法を用いて,操作を逐次スケジュールし,最適化可能な時間窓への問題分解について検討する。
論文 参考訳（メタデータ） (2022-05-16T09:33:00Z) - Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。
本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
論文 参考訳（メタデータ） (2022-01-28T05:53:28Z) - A Case Study on Optimization of Warehouses [2.2101681534594237]
倉庫では、労働者が倉庫の業績の大部分を担っている最も労働集約的でコストがかかる作業である。
本研究は,メザニン倉庫における倉庫配置の最適化と受注問題について,その相互的影響について検討する。
論文 参考訳（メタデータ） (2021-11-23T07:22:57Z) - Two-Stage Stochastic Optimization via Primal-Dual Decomposition and Deep
Unrolling [86.85697555068168]
2段階のアルゴリズム最適化は、様々な工学や科学的応用において重要な役割を果たす。
特に長期変数と短期変数が制約の中で結合されている場合、アルゴリズムは効率的ではない。
PDD-SSCAが既存のソリューションよりも優れたパフォーマンスを達成できることを示します。
論文 参考訳（メタデータ） (2021-05-05T03:36:00Z) - 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) - Constrained Multiagent Rollout and Multidimensional Assignment with the
Auction Algorithm [0.0]
本稿では,制約付き決定論的動的プログラミングに適用可能なロールアウトアルゴリズムの拡張について考察する。
提案手法では,ベースが実現可能な解を生成する場合,ロールアウトアルゴリズムはコスト改善特性を有することを示す。
コスト改善特性は計算要求を大幅に削減した代替実装で維持されていることを示す。
論文 参考訳（メタデータ） (2020-02-18T07:09:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。