CP or DP? Why Not Both: A Case Study in the Partial Shop Scheduling Problem
The paper discusses the integration of Dynamic Programming (DP) and Constraint Programming (CP) in solving the Partial Shop Scheduling Problem (PSSP). It highlights how this hybrid approach can effectively leverage the strengths of both methodologies. The authors demonstrate the flexibility of their model, which accommodates various precedence constraints and enhances solution strategies.
- ▪Dynamic Programming and Constraint Programming are typically used separately for combinatorial optimization problems.
- ▪The authors propose a hybrid approach that combines DP as the primary search framework with CP as a subroutine.
- ▪This method allows for the handling of arbitrary precedence constraints and supports anytime DP strategies.
Opening excerpt (first ~120 words) tap to expand
Computer Science > Artificial Intelligence arXiv:2605.23569 (cs) [Submitted on 22 May 2026] Title:CP or DP? Why Not Both: A Case Study in the Partial Shop Scheduling Problem Authors:Emma Legrand, Roger Kameugne, Pierre Schaus View a PDF of the paper titled CP or DP? Why Not Both: A Case Study in the Partial Shop Scheduling Problem, by Emma Legrand and Roger Kameugne and Pierre Schaus View PDF HTML (experimental) Abstract:Dynamic Programming (DP) and Constraint Programming (CP) are well-established paradigms for solving combinatorial optimization problems. Usually, these two approaches are used separately.
…
Excerpt limited to ~120 words for fair-use compliance. The full article is at arXiv cs.AI.
Discussion
0 commentsMore from arXiv cs.AI
