Domain-Independent Dynamic Programming with Constraint Propagation

• URL: http://arxiv.org/abs/2603.16648v1
• Date: Tue, 17 Mar 2026 15:19:47 GMT
• Title: Domain-Independent Dynamic Programming with Constraint Propagation
• Abstract summary: We bridge the gap between the DP and CP paradigms by integrating constraint propagation into DP.<n>We implement constraint propagation using a general-purpose CP solver in the Domain-Independent Dynamic Programming framework.<n>Our work is a key step in understanding the value of constraint propagation in DP solvers.
• Score: 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.

Related papers

• CP or DP? Why Not Both: A Case Study in the Partial Shop Scheduling Problem [1.8584311789183754]
  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.<n>The Partial Shop Scheduling Problem (PSSP) is a general scheduling problem where each job consists of a set of operations with arbitrary precedence constraints.
  arXiv  Detail & Related papers  (2026-05-22T12:36:15Z)
• Automatic Constraint Policy Optimization based on Continuous Constraint Interpolation Framework for Offline Reinforcement Learning [2.0719232729184145]
  offline Reinforcement Learning (RL) relies on policy constraints to shape performance.<n>Most existing methods commit to a single constraint family.<n>We propose Continuous Constraint Interpolation (CCI), a unified optimization framework.
  arXiv  Detail & Related papers  (2026-01-30T14:21:41Z)
• Dependency-Aware Task Offloading in Multi-UAV Assisted Collaborative Mobile Edge Computing [53.88774113545582]
  This paper presents a novel multi-unmanned aerial vehicle (UAV) assisted collaborative mobile edge computing (MEC) framework.<n>It aims to minimize the system cost, and thus realize an improved trade-off between task consumption and energy consumption.<n>We show that the proposed scheme can significantly reduce the system cost, and thus realize an improved trade-off between task consumption and energy consumption.
  arXiv  Detail & Related papers  (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]
  We present several advances to the physics and equality constrained artificial neural networks (PECANN) framework.<n>We generalize the augmented Lagrangian method (ALM) to support multiple independent penalty parameters.<n>We reformulate pointwise constraint enforcement and Lagrange multipliers as expectations over constraint terms.
  arXiv  Detail & Related papers  (2025-08-21T16:22:40Z)
• PartialLoading: User Scheduling and Bandwidth Allocation for Parameter-sharing Edge Inference [42.855714744229715]
  We develop a parameter-sharing AI model loading framework for multi-user edge inference.<n>The framework exploits two key insights: 1) the majority of latency arises from loading AI models into server GPU memory, and 2) different AI models can share a significant number of parameters.<n>We show that the proposed framework significantly improves task throughput under deadline constraints.
  arXiv  Detail & Related papers  (2025-03-29T05:58:07Z)
• M-HOF-Opt: Multi-Objective Hierarchical Output Feedback Optimization via Multiplier Induced Loss Landscape Scheduling [4.369346338392536]
  A probabilistic graphical model is proposed, modeling the joint model parameter and multiplier evolution.<n>We address multi-objective model parameter optimization via a surrogate single objective penalty loss.
  arXiv  Detail & Related papers  (2024-03-20T16:38:26Z)
• Double Duality: Variational Primal-Dual Policy Optimization for Constrained Reinforcement Learning [132.7040981721302]
  We study the Constrained Convex Decision Process (MDP), where the goal is to minimize a convex functional of the visitation measure. Design algorithms for a constrained convex MDP faces several challenges, including handling the large state space.
  arXiv  Detail & Related papers  (2024-02-16T16:35:18Z)
• Neural Stochastic Dual Dynamic Programming [99.80617899593526]
  We introduce a trainable neural model that learns to map problem instances to a piece-wise linear value function. $nu$-SDDP can significantly reduce problem solving cost without sacrificing solution quality.
  arXiv  Detail & Related papers  (2021-12-01T22:55:23Z)
• Adaptive Subcarrier, Parameter, and Power Allocation for Partitioned Edge Learning Over Broadband Channels [69.18343801164741]
  partitioned edge learning (PARTEL) implements parameter-server training, a well known distributed learning method, in wireless network. We consider the case of deep neural network (DNN) models which can be trained using PARTEL by introducing some auxiliary variables.
  arXiv  Detail & Related papers  (2020-10-08T15:27:50Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  Security-constrained optimal power flow (SCOPF) is fundamental in power systems. Modeling of APR within the SCOPF problem results in complex large-scale mixed-integer programs. This paper proposes a novel approach that combines deep learning and robust optimization techniques.
  arXiv  Detail & Related papers  (2020-07-14T12:38:21Z)
• Polynomial-Time Exact MAP Inference on Discrete Models with Global Dependencies [83.05591911173332]
  junction tree algorithm is the most general solution for exact MAP inference with run-time guarantees. We propose a new graph transformation technique via node cloning which ensures a run-time for solving our target problem independently of the form of a corresponding clique tree.
  arXiv  Detail & Related papers  (2019-12-27T13:30:29Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.