ABSTRACT. 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.

ABSTRACT. 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.

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, 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.

ABSTRACT. 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.