cs.AIFeb 22, 2020

A binarized-domains arc-consistency algorithm for TCSPs: its computational analysis and its use as a filtering procedure in solution search algorithms

Authors: Amar Isli

Organizations: University of Sciences and Technology Houari Boumedi`ene · Faculty of Computer Science · Department of Artificial Intelligence and Data Science · BP 32, Bab Ezzouar[cs.AI] DZ-16111 Algiers · Algeria

Abstract

TCSPs (Temporal Constraint Satisfaction Problems) [Dechter et al. 1991] get rid of unary constraints by binarizing them after having added an "origin of the world" variable. In this work, we look at the constraints between the "origin of the world" variable and the other variables, as the (binarized) domains of these other variables. With this in mind, we define a notion of arc-consistency for TCSPs, which we will refer to as binarized-domains Arc-Consistency, or bdArc-Consistency for short. We provide an algorithm achieving bdArc-Consistency for a TCSP, which we will refer to as bdAC-3, for it is an adaptation of Mackworth's [1977] well-known arc-consistency algorithm AC-3. We show that if an STP is bdArc-Consistent, and connected, i.e., its "origin of the world" variable is disconnected from none of the other variables, its binarized domains are minimal. We provide two polynomial backtrack-free procedures: one for the task of getting a solution from a connected bdArc-Consistent STP; the other for the task of getting, from a bdArc-Consistent STP, either that it is inconsistent or, in case of consistency, a connected bdArc-Consistent STP refinement. We then show how to use our results both in a general TCSP solver and in a TCSP-based job shop scheduler. The work also provides an experimental comparison on STPs of bdAC-3 with an existing arc-consistency algorithm, ACSTP, restricted to STPs [Kong et al. 2018]; an experimental comparison of three TCSP-based job shop schedulers, two of which use weak versions of bdAC-3 as the filtering procedure during the search, the third [Schwalb and Dechter 1997] a weak version of path-consistency; and the swi-prolog source codes used by these comparisons. Last but not least, we provide an incremental version of bdAC-3.

Explore similar work

CardsList
Jul 26, 2026cs.CC

Maximum Satisfiability of Simple Temporal Problems

The Simple Temporal Problem (STP) is a core framework for quantitative temporal constraints. As STP data can be inconsistent, we study MAXSTP: compute a maximum-cardinality consistent subset of constraints. This extension is NP-hard, and we analyze its parameterized complexity under measures that capture practically relevant instance features: the number of variables nn (instance scale), the maximum coefficient magnitude kk (numeric range), and structural parameters of the constraint graph such as treewidth twtw (decomposability) and vertex cover size vcvc (density). We show that MAXSTP is W[1]-hard parameterized by nn, implying that nn and parameters that depend on nn (including twtw and vcvc) are insufficient for fixed-parameter tractability. For combined parameters, we give an O∗(kn)O^*(k^n)-time algorithm, yielding single-exponential solvability for fixed kk. While k+twk+tw remains W[1]-hard, MAXSTP is in XP via an O∗((n⋅k)tw)O^*((n\cdot k)^{tw}) algorithm. Our results suggest that MAXSTP is often computationally harder than optimizing qualitative CSPs. We verify that many such problems (including RCC-8 and Allen's algebra) are FPT when parameterized by nn or twtw. However, we also demonstrate that FPT algorithms for MAXSTP are indeed possible but with other parameters such as k+vck + vc.
Johannes K. Fichte, Johanna Groven, Peter Jonsson +2
Satisfiability
AskPDF
May 14, 2026cs.AI

PyCSP3-Scheduling: A Scheduling Extension for PyCSP3

PyCSP3^3 provides a productive way to build constraint models for solving combinatorial constrained problems and export them to XCSP3^3, preserving a complete separation between modeling and solving. However, it lacks native support for scheduling abstractions such as interval variables, sequence variables, and resource functions. As a result, scheduling models must be encoded with low-level integer variables and manual channeling constraints, even though PyCSP3^3 already provides global constraints like NoOverlap and Cumulative on integer arrays. We present PyCSP3^3 Scheduling, a library that adds scheduling abstractions to PyCSP3^3 through 53 dedicated constraints and 27 expressions, and compiles them down to standard PyCSP3^3/XCSP3^3 constraints, maintaining the modeling/solving separation that underpins the PyCSP3^3 ecosystem. On 261 paired instances across 17 model families (5 runs each), both formulations produce identical objectives on all 72 doubly-proved optimal pairs and nearly half of the families (8/17) remain structurally unchanged after compilation; however, runtime performance diverges across families, with clear gains on some (up to 5.8x) and regressions on others due to the overhead of compilation decompositions. Code and benchmarks are available at: https://github.com/sohaibafifi/pycsp3-scheduling
Sohaib Afifi
Flexible Job-Shop SchedulingSchedulingConstraint SatisfactionHard-ConstraintComputational Chemistry
AskPDF
Jul 22, 2026cs.AI

Global Difference Constraint Propagation for Constraint Programming

Difference constraints of the form x−y≤dx - y \leq d are well studied, with efficient algorithms for satisfaction and implication, because of their connection to shortest paths. Finite domain propagation algorithms, however, typically do not make use of these algorithms, and treat each difference constraint as a separate propagator. Propagation does guarantee completeness of solving, but can be needlessly slow. In this paper we describe how to build a (bounds consistent) global propagator for difference constraints that treats them all simultaneously. SAT modulo theory solvers have included theory solvers for difference constraints for some time. While a theory solver for difference constraints gives the basis of a global difference constraint propagator, we show how the requirements on the propagator are quite different. Crucially, we show how to explain propagations by a global difference constraint propagator, in order to use it within a lazy clause generation solver. We give experiments showing that treating difference constraints globally can substantially improve on the standard propagation approach.
Lucas Kletzander, Jip J. Dekker, Andreas Schutt +1
Constraint SatisfactionSatisfiabilityDifferenceShortest PathsPropagation
AskPDF