Maximum Satisfiability of Simple Temporal Problems

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.

Optimization problems such as the NP-complete 3-SAT provide an important benchmark for the difficult task of finding ground-states in strongly correlated many-body systems with rugged energy landscapes. The study of random 3-SAT problems as Ising spin Hamiltonians in statistical physics has yielded major insights including the existence of a satisfiability phase transition, and the prediction of a critical parameter line of particularly hard instances. Yet, progress on solving those instances has been scarce for several decades. Here, introducing the Target-SAT (TSAT) algorithm, we roughly triple the tractable problem sizes in the hardest regime, with an even greater improvement in a vast range of neighboring regions. By leveraging statistical information hidden in the combinatorial constraints of the problem, TSAT is actively guided in its stochastic local search toward a target within the relevant parameter space. Our analysis also explains why established local search algorithms are limited to relatively small system sizes due to a vast low-energy trap. Furthermore, we characterize the aforementioned critical line in terms of a dominant additional complexity barrier, whose exponential scaling is quickly overcome by TSAT only in the surrounding parameter space. With TSAT, the lead in solving the hardest known random satisfiability problems returns to the realm of stochastic local search algorithms.

In this document, we introduce PyCSP$3$, a Python library that allows us to write models of combinatorial constrained problems in a declarative manner. Currently, with PyCSP$3$, you can write models of constraint satisfaction and optimization problems. More specifically, you can build CSP (Constraint Satisfaction Problem) and COP (Constraint Optimization Problem) models. Importantly, there is a complete separation between the modeling and solving phases: you write a model, you compile it (while providing some data) in order to generate an XCSP$3$ instance (file), and you solve that problem instance by means of a constraint solver. You can also directly pilot the solving procedure in PyCSP$3$, possibly conducting an incremental solving strategy. In this document, you will find all that you need to know about PyCSP$3$, with more than 50 illustrative models.