Overview

Constraint satisfaction models problems with variables, possible values, and rules that determine which combinations are allowed, helping solve tasks such as scheduling, graph coloring, and Sudoku. Classical approaches include constraint propagation and backtracking, often combined with SAT, SMT, constraint programming, or integer programming solvers. Recent work also uses graph neural networks, diffusion models, and language models to propose assignments or guide search, frequently pairing them with symbolic verification and repair. A central challenge is making learned methods reliable on genuinely hard instances and robust to changes in problem size, representation, or wording, while matching the efficiency and guarantees of classical solvers.

Latest papers

91 papers3 papers in the last four weeks, down 75% on the four weeks before. 0.0% of all new papers.

Feb 22, 2020

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

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.