Sequence Variables: A Constraint Programming Computational Domain for Routing and Sequencing

• URL: http://arxiv.org/abs/2510.09373v1
• Date: Fri, 10 Oct 2025 13:29:40 GMT
• Title: Sequence Variables: A Constraint Programming Computational Domain for Routing and Sequencing
• Authors: Augustin Delecluse, Pierre Schaus, Pascal Van Hentenryck,
• Abstract summary: This paper formalizes sequence variables within Constraint Programming (CP)<n>Unlike the classical successor models, this computational domain handle optional visits and support insertions, including insertion-based Large Neighborhood Search.<n>An implementation is described with the underlying data structures required for integrating sequence variables into existing trail-based CP solvers.
• Score: 16.6643744762214
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Constraint Programming (CP) offers an intuitive, declarative framework for modeling Vehicle Routing Problems (VRP), yet classical CP models based on successor variables cannot always deal with optional visits or insertion based heuristics. To address these limitations, this paper formalizes sequence variables within CP. Unlike the classical successor models, this computational domain handle optional visits and support insertion heuristics, including insertion-based Large Neighborhood Search. We provide a clear definition of their domain, update operations, and introduce consistency levels for constraints on this domain. An implementation is described with the underlying data structures required for integrating sequence variables into existing trail-based CP solvers. Furthermore, global constraints specifically designed for sequence variables and vehicle routing are introduced. Finally, the effectiveness of sequence variables is demonstrated by simplifying problem modeling and achieving competitive computational performance on the Dial-a-Ride Problem.

Related papers

• Subgoaling Relaxation-based Heuristics for Numeric Planning with Infinite Actions [11.009425634308043]
  Planning with control parameters extends the standard numeric planning model by introducing action parameters as free numeric variables.<n>In this setting, off-the-shelf numerics that leverage the action structure are not feasible.<n>We propose an optimistic compilation approach that transforms simple numeric problems into simple numeric tasks.
  arXiv  Detail & Related papers  (2025-12-26T20:05:57Z)
• A Clustering-Based Variable Ordering Framework for Relaxed Decision Diagrams for Maximum Weighted Independent Set Problem [4.312746668772342]
  This work introduces a novel clustering-based framework for variable ordering.<n>Instead of applying dynamic orderings to the full set of unfixed variables, we first primal variables into clusters.<n>We then leverage this structural decomposition to guide the ordering process, significantly reducing the partition's search space.
  arXiv  Detail & Related papers  (2025-12-17T08:49:38Z)
• Adapformer: Adaptive Channel Management for Multivariate Time Series Forecasting [49.40321003932633]
  Adapformer is an advanced Transformer-based framework that merges the benefits of CI and CD methodologies through effective channel management.<n>Adapformer achieves superior performance over existing models, enhancing both predictive accuracy and computational efficiency.
  arXiv  Detail & Related papers  (2025-11-18T16:24:05Z)
• Hierarchical Modeling and Architecture Optimization: Review and Unified Framework [0.6291443816903801]
  This paper reviews literature on structured input spaces and proposes a unified framework that generalizes existing approaches.<n>A variable is described as meta if its value governs the presence of other decreed variables, enabling the modeling of conditional and hierarchical structures.
  arXiv  Detail & Related papers  (2025-06-27T20:38:57Z)
• An Expansion-Based Approach for Quantified Integer Programming [0.0]
  Quantified Programming (QIP) bridges multiple domains by extending Quantified Boolean Formulas (QBF)<n>QIP provides a versatile framework for addressing complex decision-making scenarios.<n>We introduce an expansion-based approach for QIP using Counterexample-Guided Abstraction Refinement (CEGAR)
  arXiv  Detail & Related papers  (2025-06-04T21:14:14Z)
• Q-function Decomposition with Intervention Semantics with Factored Action Spaces [51.01244229483353]
  We consider Q-functions defined over a lower dimensional projected subspace of the original action space, and study the condition for the unbiasedness of decomposed Q-functions.<n>This leads to a general scheme which we call action decomposed reinforcement learning that uses the projected Q-functions to approximate the Q-function in standard model-free reinforcement learning algorithms.
  arXiv  Detail & Related papers  (2025-04-30T05:26:51Z)
• Partial Transportability for Domain Generalization [56.37032680901525]
  Building on the theory of partial identification and transportability, this paper introduces new results for bounding the value of a functional of the target distribution.<n>Our contribution is to provide the first general estimation technique for transportability problems.<n>We propose a gradient-based optimization scheme for making scalable inferences in practice.
  arXiv  Detail & Related papers  (2025-03-30T22:06:37Z)
• Domain-Incremental Semantic Segmentation for Autonomous Driving under Adverse Driving Conditions [14.2843647693986]
  We propose an architecture-based domain-incremental learning approach called Progressive Semantic (PSS)<n>PSS is a task-agnostic, dynamically growing collection of domain-specific segmentation models.<n>We extensively evaluate our proposed approach using several datasets at varying levels of generalization in the categorization of adverse driving conditions.
  arXiv  Detail & Related papers  (2025-01-09T13:54:59Z)
• Last-Iterate Global Convergence of Policy Gradients for Constrained Reinforcement Learning [62.81324245896717]
  We introduce an exploration-agnostic algorithm, called C-PG, which exhibits global last-ite convergence guarantees under (weak) gradient domination assumptions. We numerically validate our algorithms on constrained control problems, and compare them with state-of-the-art baselines.
  arXiv  Detail & Related papers  (2024-07-15T14:54:57Z)
• HCVP: Leveraging Hierarchical Contrastive Visual Prompt for Domain Generalization [69.33162366130887]
  Domain Generalization (DG) endeavors to create machine learning models that excel in unseen scenarios by learning invariant features. We introduce a novel method designed to supplement the model with domain-level and task-specific characteristics. This approach aims to guide the model in more effectively separating invariant features from specific characteristics, thereby boosting the generalization.
  arXiv  Detail & Related papers  (2024-01-18T04:23:21Z)
• Order-preserving Consistency Regularization for Domain Adaptation and Generalization [45.64969000499267]
  Deep learning models fail on cross-domain challenges if the model is oversensitive to domain-specific attributes. We propose the Order-preserving Consistency Regularization (OCR) for cross-domain tasks.
  arXiv  Detail & Related papers  (2023-09-23T04:45:42Z)
• Goal Kernel Planning: Linearly-Solvable Non-Markovian Policies for Logical Tasks with Goal-Conditioned Options [54.40780660868349]
  We introduce a compositional framework called Linearly-Solvable Goal Kernel Dynamic Programming (LS-GKDP)<n>LS-GKDP combines the Linearly-Solvable Markov Decision Process (LMDP) formalism with the Options Framework of Reinforcement Learning.<n>We show how an LMDP with a goal kernel enables the efficient optimization of meta-policies in a lower-dimensional subspace defined by the task grounding.
  arXiv  Detail & Related papers  (2020-07-06T05:13:20Z)
• Supervised Learning for Non-Sequential Data: A Canonical Polyadic Decomposition Approach [85.12934750565971]
  Efficient modelling of feature interactions underpins supervised learning for non-sequential tasks. To alleviate this issue, it has been proposed to implicitly represent the model parameters as a tensor. For enhanced expressiveness, we generalize the framework to allow feature mapping to arbitrarily high-dimensional feature vectors.
  arXiv  Detail & Related papers  (2020-01-27T22:38:40Z)

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.