Workshop Program

We propose a solver-in-the-loop self-improvement framework for training neural policies to guide domain-independent dynamic programming (DIDP) in solving combinatorial optimization problems. For each instance, DIDP-based beam search is run within a DIDP model, leveraging its pruning mechanisms such as dual bounds and state constraints, and the best solution found is extracted as an expert trajectory. The policy is then trained by minimizing a cross-entropy imitation loss. Experiments on the four combinatorial optimization problems show that the proposed method consistently reduces node expansions and achieves competitive solve time, while significantly outperforming the same DIDP models and solvers guided by Proximal Policy Optimization (PPO) and by the default dual bound guidance.

Download PDF

To be presented at ICAPS 2026.

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 (1|ri,δi| wiTi), 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 1|ri,δi| wiTi 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.

Dynamic programming solvers in existence today combine a modeling language with fixed search algorithms. While they allow model-specific heuristics, their ability to experiment with different search strategies remains limited. This paper introduces an extension to CODD that implements novel and classic search strategies, using the common modeling language of CODD. It also investigates an implicit diagram representation that reduces memory usage and improves performance. Experimental results on several classic combinatorial optimization problems demonstrate the importance of easily switching search strategies.

Download PDF

Dynamic programming (DP) outperforms other optimization methods for learning decision trees by several orders of magnitude in runtime because it can exploit the fact that subtrees can be solved independently from one another. We explore the use of DP for optimizing decision tree in four dimensions: first, we recollect that decision tree learning is best described as an AND-OR optimization problem, in contrast to the more typical OR variant; second, we examine the conditions for objectives and constraints such subtrees can be solved independently; third, we show how reasoning about subproblem similarity helps prune the search space; and fourth, we show how DP can be used to find not only the optimal but all close-to-optimal solutions efficiently.

Presented at CPAIOR 2026.

We present a GPU-accelerated method for compiling multi-valued decision diagrams (MDDs) for dynamic programming models. MDD construction expands states in layers defined by their distance from the root, a structure that enables independent parallel expansion of all states in a layer. We exploit this by partitioning each layer into limited-size fragments and executing the full expansion of each fragment on the GPU, including successor generation, dominance filtering, duplicate elimination, and pruning of suboptimal states. By systematically traversing fragments in a depth-first manner, we obtain a parallel Complete Anytime Decision Diagram Search that preserves exactness and anytime behavior. Applied to the Traveling Salesman Problem with Time Windows, our implementation yields speedups of up to two orders of magnitude, and outperforms other state-based methods as well as a state-of-the-art dedicated optimization method for this application.

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, providing an alternative way to address the problem, 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. 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.

Download PDF

We study the Type-I assembly line balancing problem with human-robot collaboration (Type-I ALBP-HRC), which jointly requires task-to-station assignment, robot allocation, execution-mode selection (human, robot, or collaborative), and intra-station scheduling under precedence constraints. We develop and compare two independent exact approaches for this problem: a constraint programming (CP) model exploiting interval-based scheduling constraints and a dynamic programming (DP) approach built on a three-level nested dynamic program. Both approaches are benchmarked against a MIP reference model on standard instances. Results show that DP-based engines are strongly competitive for proof-oriented exact search, while CP methods provide tight optimality gaps on hard, large instances within time limits.

Download PDF

Column elimination is a technique recently introduced to solve optimization problems aiming to find an optimal set of sequences, such as vehicle routing problems. It relies a compact representation of the problem in the form of a relaxed decision diagram, from which a relaxed solution can be extracted by solving a constrained network flow problem. As long as the solution contains infeasible sequences, or sequences with an under-approximated cost, the decision diagram is refined to eliminate the corresponding conflicts. This paper describes the ingredients required to apply column elimination to scheduling problems and presents preliminary results.