論文の概要: Domain-Independent Dynamic Programming with Constraint Propagation
- arxiv url: http://arxiv.org/abs/2603.16648v1
- Date: Tue, 17 Mar 2026 15:19:47 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-03-18 17:42:07.364442
- Title: Domain-Independent Dynamic Programming with Constraint Propagation
- Title（参考訳）: 制約伝搬を用いたドメインに依存しない動的プログラミング
- Authors: Imko Marijnissen, J. Christopher Beck, Emir Demirović, Ryo Kuroiwa,
- Abstract要約: 制約伝搬をDPに統合することで,DPとCPのパラダイムのギャップを埋める。
ドメインに依存しない動的プログラミングフレームワークにおいて,汎用CPソルバを用いた制約伝搬を実装した。
我々の研究は、DPソルバにおける制約伝播の価値を理解するための重要なステップである。
- 参考スコア（独自算出の注目度）: 5.18980781199159
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: There are two prevalent model-based paradigms for combinatorial problems: 1) state-based representations, such as heuristic search, dynamic programming (DP), and decision diagrams, and 2) constraint and domain-based representations, such as constraint programming (CP), (mixed-)integer programming, and Boolean satisfiability. In this paper, we bridge the gap between the DP and CP paradigms by integrating constraint propagation into DP, enabling a DP solver to prune states and transitions using constraint propagation. To this end, we implement constraint propagation using a general-purpose CP solver in the Domain-Independent Dynamic Programming framework and evaluate using heuristic search on three combinatorial optimisation problems: Single Machine Scheduling with Time Windows, the Resource Constrained Project Scheduling Problem (RCPSP), and the Travelling Salesperson Problem with Time Windows (TSPTW). Our evaluation shows that constraint propagation significantly reduces the number of state expansions, causing our approach to solve more instances than a DP solver for Single Machine Scheduling and RCPSP, and showing similar improvements for tightly constrained TSPTW instances. The runtime performance indicates that the benefits of propagation outweigh the overhead for constrained instances, but that further work into reducing propagation overhead could improve performance further. Our work is a key step in understanding the value of constraint propagation in DP solvers, providing a model-based approach to integrating DP and CP.
- Abstract（参考訳）: 組合せ問題には2つの一般的なモデルベースパラダイムがある。
1)ヒューリスティック検索、動的プログラミング(DP)、意思決定図などの状態ベース表現
2)制約プログラミング(CP)、(混合)整数プログラミング、ブール適合性など、制約とドメインベースの表現。
本稿では,制約伝搬をDPに統合することにより,DPとCPのパラダイム間のギャップを埋める。
この目的のために、ドメイン独立動的プログラミングフレームワークにおいて汎用CPソルバを用いて制約伝搬を実装し、時間Windowsによるシングルマシンスケジューリング、資源制約計画スケジューリング問題(RCPSP)、時間Windowsによるトラベリングセールスパーソン問題(TSPTW)という3つの組合せ最適化問題のヒューリスティック探索を用いて評価する。
評価の結果,制約伝搬は状態拡張数を著しく減少させ,単一マシンスケジューリングやRCPSPのDP解決よりも多くのインスタンスを解決し,TSPTWインスタンスを厳格に制限した上で同様の改善が見られた。
実行時のパフォーマンスは、伝搬の利点が制約されたインスタンスのオーバーヘッドよりも優れていることを示しているが、伝播のオーバーヘッドを減らすためのさらなる作業は、パフォーマンスをさらに向上させる可能性がある。
我々の研究は、DPソルバにおける制約伝播の価値を理解するための重要なステップであり、DPとCPを統合するためのモデルベースのアプローチを提供する。
関連論文リスト
- Automatic Constraint Policy Optimization based on Continuous Constraint Interpolation Framework for Offline Reinforcement Learning [2.0719232729184145]
オフライン強化学習(RL)は、パフォーマンスを形作るためのポリシー制約に依存している。
既存のほとんどのメソッドは単一の制約ファミリにコミットします。
本稿では,統合最適化フレームワークであるContinuous Constraint Interpolation (CCI)を提案する。
論文 参考訳（メタデータ） (2026-01-30T14:21:41Z) - Dependency-Aware Task Offloading in Multi-UAV Assisted Collaborative Mobile Edge Computing [53.88774113545582]
本稿では,新しい無人航空機(UAV)による協調移動エッジコンピューティング(MEC)フレームワークを提案する。
システムコストを最小限に抑え、タスク消費とエネルギー消費のトレードオフを改善することを目的としている。
提案手法はシステムコストを大幅に削減し,タスク消費とエネルギー消費のトレードオフの改善を実現する。
論文 参考訳（メタデータ） (2025-10-23T02:55:40Z) - Conditionally adaptive augmented Lagrangian method for physics-informed learning of forward and inverse problems using artificial neural networks [0.24578723416255746]
本稿では,物理・等式制約付きニューラルネットワーク(PECANN)フレームワークについて述べる。
拡張ラグランジアン法(ALM)を一般化し、複数の独立ペナルティパラメータをサポートする。
我々は、制約項に対する期待として、ポイントワイズ制約強制とラグランジュ乗算を再構成する。
論文 参考訳（メタデータ） (2025-08-21T16:22:40Z) - PartialLoading: User Scheduling and Bandwidth Allocation for Parameter-sharing Edge Inference [42.855714744229715]
マルチユーザエッジ推論のためのパラメータ共有AIモデルローディングフレームワークを開発した。
1) レイテンシの大部分は、AIモデルをサーバGPUメモリにロードすることで発生し、2) 異なるAIモデルは、かなりの数のパラメータを共有できる。
提案手法は納期制約下でのタスクスループットを大幅に改善することを示す。
論文 参考訳（メタデータ） (2025-03-29T05:58:07Z) - M-HOF-Opt: Multi-Objective Hierarchical Output Feedback Optimization via Multiplier Induced Loss Landscape Scheduling [4.369346338392536]
連立モデルパラメータと乗算器の進化をモデル化した確率的グラフィカルモデルを提案する。
代用単目的ペナルティ損失による多目的モデルパラメータ最適化に対処する。
論文 参考訳（メタデータ） (2024-03-20T16:38:26Z) - Double Duality: Variational Primal-Dual Policy Optimization for
Constrained Reinforcement Learning [132.7040981721302]
本研究では,訪問尺度の凸関数を最小化することを目的として,制約付き凸決定プロセス(MDP)について検討する。
制約付き凸MDPの設計アルゴリズムは、大きな状態空間を扱うなど、いくつかの課題に直面している。
論文 参考訳（メタデータ） (2024-02-16T16:35:18Z) - Neural Stochastic Dual Dynamic Programming [99.80617899593526]
我々は、問題インスタンスを断片的線形値関数にマッピングすることを学ぶトレーニング可能なニューラルモデルを導入する。
$nu$-SDDPは、ソリューションの品質を犠牲にすることなく、問題解決コストを大幅に削減できる。
論文 参考訳（メタデータ） (2021-12-01T22:55:23Z) - Adaptive Subcarrier, Parameter, and Power Allocation for Partitioned
Edge Learning Over Broadband Channels [69.18343801164741]
パーティショニングエッジ学習(PARTEL)は、無線ネットワークにおいてよく知られた分散学習手法であるパラメータサーバトレーニングを実装している。
本稿では、いくつかの補助変数を導入してParticleELを用いてトレーニングできるディープニューラルネットワーク(DNN)モデルについて考察する。
論文 参考訳（メタデータ） (2020-10-08T15:27:50Z) - Combining Deep Learning and Optimization for Security-Constrained
Optimal Power Flow [94.24763814458686]
セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。
SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。
本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
論文 参考訳（メタデータ） (2020-07-14T12:38:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。