論文の概要: Domain-Independent Dynamic Programming: Generic State Space Search for
Combinatorial Optimization
- arxiv url: http://arxiv.org/abs/2211.14409v1
- Date: Sat, 26 Nov 2022 00:15:45 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-29 17:45:44.895519
- Title: Domain-Independent Dynamic Programming: Generic State Space Search for
Combinatorial Optimization
- Title(参考訳): ドメインに依存しない動的プログラミング: 組合せ最適化のためのジェネリック状態空間探索
- Authors: Ryo Kuroiwa and J. Christopher Beck
- Abstract要約: 動的プログラミング(DP)に基づく新しいモデルベースパラダイムであるドメイン非依存動的プログラミング(DIDP)を提案する。
DPモデルを定義するフォーマリズムである動的プログラミング記述言語(DyPDL)を提案し、DyP(CAASDy)のためのコスト代数型A*ソルバーを開発する。
- 参考スコア(独自算出の注目度): 13.386517072025722
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: For combinatorial optimization problems, model-based approaches such as
mixed-integer programming (MIP) and constraint programming (CP) aim to decouple
modeling and solving a problem: the 'holy grail' of declarative problem
solving. We propose domain-independent dynamic programming (DIDP), a new
model-based paradigm based on dynamic programming (DP). While DP is not new, it
has typically been implemented as a problem-specific method. We propose Dynamic
Programming Description Language (DyPDL), a formalism to define DP models, and
develop Cost-Algebraic A* Solver for DyPDL (CAASDy), a generic solver for DyPDL
using state space search. We formalize existing problem-specific DP and state
space search methods for combinatorial optimization problems as DP models in
DyPDL. Using CAASDy and commercial MIP and CP solvers, we experimentally
compare the DP models with existing MIP and CP models, showing that, despite
its nascent nature, CAASDy outperforms MIP and CP on a number of common problem
classes.
- Abstract(参考訳): 組合せ最適化問題では、混合整数プログラミング (MIP) や制約プログラミング (CP) といったモデルベースのアプローチがモデリングと問題解決を分離することを目的としている。
本稿では、動的プログラミング(DP)に基づく新しいモデルベースパラダイムであるドメイン独立動的プログラミング(DIDP)を提案する。
DPは新しいものではないが、通常は問題固有の方法として実装されている。
我々はDPモデルを定義するための形式である動的プログラミング記述言語(DyPDL)を提案し、状態空間探索を用いたDyPDLの汎用解法であるDyPDL用コスト代数型A*ソルバー(CAASDy)を開発した。
我々はDyPDLのDPモデルとして既存の問題固有DPと状態空間探索法を定式化した。
CAASDy と商用 MIP と CP の解法を用いて,DP モデルと既存の MIP と CP モデルとを実験的に比較した結果,CAASDy は初期の性質にもかかわらず,多くの共通問題クラスにおいて MIP と CP よりも優れていることがわかった。
関連論文リスト
- Sample Complexity Characterization for Linear Contextual MDPs [67.79455646673762]
文脈決定プロセス(CMDP)は、遷移カーネルと報酬関数がコンテキスト変数によってインデックス付けされた異なるMDPで時間とともに変化できる強化学習のクラスを記述する。
CMDPは、時間とともに変化する環境で多くの現実世界のアプリケーションをモデル化するための重要なフレームワークとして機能する。
CMDPを2つの線形関数近似モデルで検討する: 文脈変化表現とすべての文脈に対する共通線形重み付きモデルIと、すべての文脈に対する共通表現と文脈変化線形重み付きモデルIIである。
論文 参考訳(メタデータ) (2024-02-05T03:25:04Z) - Domain-Independent Dynamic Programming [6.437469175415774]
ドメイン独立動的プログラミング(DIDP)は動的プログラミング(DP)に基づく新しいモデルベースパラダイムである
AI計画にインスパイアされた状態遷移システムに基づくDPモデルを定義するフォーマリズムである動的プログラミング記述言語(DyPDL)を導入する。
探索アルゴリズムを用いてDyPDLモデルの解法と7つのDIDP解法を提案する。
論文 参考訳(メタデータ) (2024-01-25T01:48:09Z) - DIMES: A Differentiable Meta Solver for Combinatorial Optimization
Problems [41.57773395100222]
深部強化学習(DRL)モデルはNP-hard Combinatorial Optimization問題を解決する上で有望な結果を示している。
本稿では,DIMESという新しいアプローチを提案することによって,大規模最適化におけるスケーラビリティの課題に対処する。
コストのかかる自己回帰的復号法や離散解の反復的洗練に苦しむ従来のDRL法とは異なり、DIMESは候補解の基底分布をパラメータ化するためのコンパクトな連続空間を導入する。
DIMESは、トラベリングセールスマン問題や最大独立セット問題のための大規模なベンチマークデータセットにおいて、最近のDRLベースの手法よりも優れていることを示す。
論文 参考訳(メタデータ) (2022-10-08T23:24:37Z) - Multi-Objective Policy Gradients with Topological Constraints [108.10241442630289]
本稿では, PPOアルゴリズムの簡単な拡張により, TMDPにおけるポリシー勾配に対する新しいアルゴリズムを提案する。
シミュレーションと実ロボットの両方の目的を任意に並べた実世界の多目的ナビゲーション問題に対して,これを実証する。
論文 参考訳(メタデータ) (2022-09-15T07:22:58Z) - Linear programming-based solution methods for constrained POMDPs [0.5156484100374059]
制約付き部分観測可能なマルコフ決定過程(CPOMDP)は、様々な実世界の現象をモデル化するために用いられている。
我々は、CPOMDPの近似ポリシーを生成するために、グリッドベースの近似と線形プログラミング(LP)モデルを組み合わせる。
論文 参考訳(メタデータ) (2022-06-28T15:22:24Z) - Neural Stochastic Dual Dynamic Programming [99.80617899593526]
我々は、問題インスタンスを断片的線形値関数にマッピングすることを学ぶトレーニング可能なニューラルモデルを導入する。
$nu$-SDDPは、ソリューションの品質を犠牲にすることなく、問題解決コストを大幅に削減できる。
論文 参考訳(メタデータ) (2021-12-01T22:55:23Z) - A review of approaches to modeling applied vehicle routing problems [77.34726150561087]
車両経路問題のモデル化手法について概説する。
モデリング手法を評価するためのいくつかの基準を定式化する。
我々はVRPドメインのモデリング分野における今後の研究の道について論じる。
論文 参考訳(メタデータ) (2021-05-23T14:50:14Z) - Deep Policy Dynamic Programming for Vehicle Routing Problems [89.96386273895985]
本稿では,学習ニューラルの強みと動的プログラミングアルゴリズムの強みを組み合わせた深層ポリシー動的プログラミング(d pdp)を提案する。
D PDPは、例の解からエッジを予測するために訓練されたディープニューラルネットワークから派生したポリシーを使用して、DP状態空間を優先し、制限する。
本研究では,旅行セールスマン問題 (TSP) と車両ルーティング問題 (VRP) の枠組みを評価し,ニューラルネットワークが(制限された)DPアルゴリズムの性能を向上させることを示す。
論文 参考訳(メタデータ) (2021-02-23T15:33:57Z) - GACEM: Generalized Autoregressive Cross Entropy Method for Multi-Modal
Black Box Constraint Satisfaction [69.94831587339539]
本稿では,マスク付き自己回帰ニューラルネットワークを用いて解空間上の均一分布をモデル化するクロスエントロピー法(CEM)を提案する。
我々のアルゴリズムは複雑な解空間を表現でき、様々な異なる解領域を追跡できる。
論文 参考訳(メタデータ) (2020-02-17T20:21:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。