論文の概要: CP or DP? Why Not Both: A Case Study in the Partial Shop Scheduling Problem
- arxiv url: http://arxiv.org/abs/2605.23569v1
- Date: Fri, 22 May 2026 12:36:15 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-05-25 17:29:20.346579
- Title: CP or DP? Why Not Both: A Case Study in the Partial Shop Scheduling Problem
- Title（参考訳）: CP か DP か? 両方ではない: 部分的な店舗スケジューリング問題におけるケーススタディ
- Authors: Emma Legrand, Roger Kameugne, Pierre Schaus,
- Abstract要約: 本稿では,DPが主探索フレームワークとして機能し,CPがサブルーチンとして機能し,グローバルな制約伝搬を活用することによって,両者を効果的かつエレガントに組み合わせることができることを示す。
部分店スケジューリング問題(Partial Shop Scheduling Problem、PSSP)は、ジョブが任意の優先順位制約を持つ一連の操作からなる一般的なスケジューリング問題である。
- 参考スコア（独自算出の注目度）: 1.8584311789183754
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Dynamic Programming (DP) and Constraint Programming (CP) are well-established paradigms for solving combinatorial optimization problems. Usually, these two approaches are used separately. This paper aims to show that the two can be combined effectively and elegantly, with DP serving as the primary search framework and CP used as a subroutine to leverage global constraint propagation. This paper presents such an approach for the Partial Shop Scheduling Problem (PSSP), for which a pure DP method has previously been proposed, and efficient CP filtering algorithms are available. The PSSP is a general scheduling problem where each job consists of a set of operations with arbitrary precedence constraints. The approach is flexible enough to accommodate anytime DP strategies, such as anytime column search, whereas the original DP algorithm operated in a strictly layer-wise manner. Moreover, the flexibility of the CP modeling makes it straightforward to incorporate arbitrary precedence constraints. As a result, the model naturally handles any precedence graph and even enables the design of a Large Neighborhood Search (LNS) scheme, in which the DP model is reused, and partial-order schedules are imposed across restarts to improve the incumbent solution. While not competitive with state-of-the-art pure CP solvers for this specific problem, our primary contribution is demonstrating the viability of this hybrid integration.
- Abstract（参考訳）: 動的プログラミング(DP)と制約プログラミング(CP)は組合せ最適化問題の解法として確立されたパラダイムである。
通常、これら2つのアプローチは別々に使用される。
本稿では,DPが主探索フレームワークとして機能し,CPがサブルーチンとして機能し,グローバルな制約伝搬を活用することによって,両者を効果的かつエレガントに組み合わせることができることを示す。
本稿では, パーシャルショップスケジューリング問題 (PSSP) に対して, 純粋DP法が提案されており, 効率的なCPフィルタリングアルゴリズムが利用可能であることを示す。
PSSPは、各ジョブが任意の優先順位制約を持つ一連の操作からなる一般的なスケジューリング問題である。
この手法は、任意の時間列探索などのDP戦略に対応するのに十分柔軟であるが、元のDPアルゴリズムは厳密に階層的に動作している。
さらに、CPモデリングの柔軟性により、任意の優先順位制約を簡単に組み込むことができる。
その結果、モデルは自然に先行グラフを処理し、DPモデルを再利用するLarge Neighborhood Search(LNS)スキームの設計を可能にし、既存のソリューションを改善するために再起動毎に部分順序スケジュールが課される。
この特定の問題に対して、最先端の純粋なCPソルバと競合することはないが、我々の主な貢献は、このハイブリッド統合の可能性を実証することである。
関連論文リスト
- Domain-Independent Dynamic Programming with Constraint Propagation [5.18980781199159]
制約伝搬をDPに統合することで,DPとCPのパラダイムのギャップを埋める。
ドメインに依存しない動的プログラミングフレームワークにおいて,汎用CPソルバを用いた制約伝搬を実装した。
我々の研究は、DPソルバにおける制約伝播の価値を理解するための重要なステップである。
論文 参考訳（メタデータ） (2026-03-17T15:19:47Z) - Adaptive Bias Generalized Rollout Policy Adaptation on the Flexible Job-Shop Scheduling Problem [3.6266514127975906]
フレキシブルジョブショップスケジューリング問題(FJSSP)はNPハード最適化問題である。
一般化Nested Rollout Policy Adaptationから派生した新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2025-05-13T11:27:18Z) - Individualized Privacy Accounting via Subsampling with Applications in Combinatorial Optimization [55.81991984375959]
本研究では、以下の簡単な観察を通して、個別化されたプライバシ会計を解析する新しい手法を提案する。
我々は、分解可能な部分モジュラーおよびセットアルゴリズム被覆を含む、プライベート最適化問題に対するいくつかの改良されたアルゴリズムを得る。
論文 参考訳（メタデータ） (2024-05-28T19:02:30Z) - Provably Efficient UCB-type Algorithms For Learning Predictive State
Representations [55.00359893021461]
逐次決定問題は、予測状態表現(PSR)によってモデル化された低ランク構造が認められる場合、統計的に学習可能である
本稿では,推定モデルと実モデル間の全変動距離を上限とする新しいボーナス項を特徴とする,PSRに対する最初のUCB型アプローチを提案する。
PSRに対する既存のアプローチとは対照的に、UCB型アルゴリズムは計算的トラクタビリティ、最優先の準最適ポリシー、モデルの精度が保証される。
論文 参考訳（メタデータ） (2023-07-01T18:35:21Z) - 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) - Domain-Independent Dynamic Programming: Generic State Space Search for
Combinatorial Optimization [13.386517072025722]
動的プログラミング(DP)に基づく新しいモデルベースパラダイムであるドメイン非依存動的プログラミング(DIDP)を提案する。
DPモデルを定義するフォーマリズムである動的プログラミング記述言語(DyPDL)を提案し、DyP(CAASDy)のためのコスト代数型A*ソルバーを開発する。
論文 参考訳（メタデータ） (2022-11-26T00:15:45Z) - Multi-Objective Policy Gradients with Topological Constraints [108.10241442630289]
本稿では, PPOアルゴリズムの簡単な拡張により, TMDPにおけるポリシー勾配に対する新しいアルゴリズムを提案する。
シミュレーションと実ロボットの両方の目的を任意に並べた実世界の多目的ナビゲーション問題に対して,これを実証する。
論文 参考訳（メタデータ） (2022-09-15T07:22:58Z) - COPS: Controlled Pruning Before Training Starts [68.8204255655161]
最先端のディープニューラルネットワーク(DNN)プルーニング技術は、トレーニング開始前にワンショットで適用され、プルーニングスコアと呼ばれる単一の基準の助けを借りてスパースアーキテクチャを評価する。
この作業では、単一プルーニング基準に集中するのではなく、任意のGASを組み合わせてより強力なプルーニング戦略を構築するためのフレームワークを提供します。
論文 参考訳（メタデータ） (2021-07-27T08:48:01Z) - Combining Deep Learning and Optimization for Security-Constrained
Optimal Power Flow [94.24763814458686]
セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。
SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。
本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
論文 参考訳（メタデータ） (2020-07-14T12:38:21Z) - Goal Kernel Planning: Linearly-Solvable Non-Markovian Policies for Logical Tasks with Goal-Conditioned Options [54.40780660868349]
我々はLinearly-Solvable Goal Kernel Dynamic Programming (LS-GKDP)と呼ばれる合成フレームワークを導入する。
LS-GKDPは、Linearly-Solvable Markov Decision Process (LMDP)形式とOptions Framework of Reinforcement Learningを組み合わせたものである。
本稿では,目標カーネルを持つLMDPが,タスク接地によって定義された低次元部分空間におけるメタポリティシの効率的な最適化を実現する方法を示す。
論文 参考訳（メタデータ） (2020-07-06T05:13:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。