Constraint satisfaction problems form an important and wide class of combinatorial search and optimization problems with many applications in AI and other areas. We introduce a recurrent neural network architecture RUN-CSP (Recurrent Unsupervised Neural Network for Constraint Satisfaction Problems) to train message passing networks solving binary constraint satisfaction problems (CSPs) or their optimization versions (Max-CSP). The architecture is universal in the sense that it works for all binary CSPs: depending on the constraint language, we can automtically design a loss function, which is then used to train generic neural nets. In this paper, we experimentally evaluate our approach for the 3-colorability problem (3-Col) and its optimization version (Max-3-Col) and for the maximum 2-satisfiability problem (Max-2-Sat). We also extend the framework to work for related optimization problems such as the maximum independent set problem (Max-IS). Training is unsupervised, we train the network on arbitrary (unlabeled) instances of the problems. Moreover, we experimentally show that it suffices to train on relatively small instances; the resulting message passing network will perform well on much larger instances (at least 10-times larger).

In this thesis, we introduce a novel formal framework to represent and reason about qualitative direction and distance relations between extended objects using Answer Set Programming (ASP). We take Cardinal Directional Calculus (CDC) as a starting point and extend CDC with new sorts of constraints which involve defaults, preferences and negation. We call this extended version as nCDC. Then we further extend nCDC by augmenting qualitative distance relation and name this extension as nCDC+. For CDC, nCDC, nCDC+, we introduce an ASP-based general framework to solve consistency checking problems, address composition and inversion of qualitative spatial relations, infer unknown or missing relations between objects, and find a suitable configuration of objects which fulfills a given inquiry.

The job-shop scheduling is one of the most studied optimization problems from the dawn of computer era to the present day. Its combinatorial nature makes it easily expressible as a constraint satisfaction problem. In this paper, we compare the performance of two constraint solvers on the job-shop scheduling problem. The solvers in question are: OR-Tools, an open-source solver developed by Google and winner of the last MiniZinc Challenge, and CP Optimizer, a proprietary IBM constraint solver targeted at industrial scheduling problems. The comparison is based on the goodness of the solutions found and the time required to solve the problem instances. First, we target the classic benchmarks from the literature, then we carry out the comparison on a benchmark that was created with known optimal solution, with size comparable to real-world industrial problems.

Barichard & I. St ephan This work is licensed under the Creative Commons Attribution License. Quantified Constraint Handling Rules Vincent Barichard LERIA, University of Angers Angers, France vincent.barichard@univ-angers.fr Igor St ephan LERIA, University of Angers Angers, France igor.stephan@univ-angers.fr We shift the QCSP (Quantified Constraint Satisfaction Problems) framework to the QCHR (Quantified Constraint Handling Rules) framework by enabling dynamic binder and access to user-defined constraints. QCSP offers a natural framework to express PSP ACE problems as finite two-players games. But to define a QCSP model, the binder must be formerly known and cannot be built dynamically even if the worst case won't occur. To overcome this issue, we define the new QCHR formalism that allows to build the binder dynamically during the solving. Our QCHR models exhibit state-of-the-art performances on static binder and outperforms previous QCSP approaches when the binder is dynamic. 1 Introduction We shift the QCSP (for Quantified Constraint Satisfaction Problems) framework to the QCHR (for Quantified Constraint Handling Rule) framework. Such shift is motivated by the difficulties for developing real applications in QCSP . QCSP [7, 26, 15, 4, 22, 20, 3] are a generalization of Constraint Satisfaction Problems (CSP) in which variables may be quantified existentially (as in CSP) and universally. A QCSP is an alternation of existentially and universally quantified variables over finite domains, the binder, followed by a CSP . Universally quantified variables represent uncontrollable parameters such as meteorological events.

We investigate conjunctive normal form (CNF) encodings of a function represented with a smooth decomposable negation normal form (DNNF). Several encodings of DNNFs and decision diagrams were considered by (Abio et al. 2016). The authors differentiate between encodings which implement consistency or domain consistency from encodings which implement unit refutation completeness or propagation completeness (in both cases implements means by unit propagation). The difference is that in the former case we do not care about properties of the encoding with respect to the auxiliary variables while in the latter case we treat all variables (the input ones and the auxiliary ones) in the same way. The latter case is useful if a DNNF is a part of a problem containing also other constraints and a SAT solver is used to test satisfiability. The currently known encodings of smooth DNNF theories implement domain consistency. Building on this and the result of (Abio et al. 2016) on an encoding of decision diagrams which implements propagation completeness, we present a new encoding of a smooth DNNF which implements propagation completeness. This closes the gap left open in the literature on encodings of DNNFs.

Distributed Pseudo-tree Optimization Procedure (DPOP) is a well-known message passing algorithm that has been used to provide optimal solutions of Distributed Constraint Optimization Problems (DCOPs) -- a framework that is designed to optimize constraints in cooperative multi-agent systems. The traditional DCOP formulation does not consider those constraints that must be satisfied (also known as hard constraints), rather it concentrates only on soft constraints. However, the presence of both types of constraints are observed in a number of applications, such as Distributed Radio Link Frequency Assignment and Distributed Event Scheduling, etc. Although the combination of these types of constraints is recently incorporated in DPOP to solve DCOPs, scalability remains an issue for them as finding an optimal solution is NP-hard. Additionally, in DPOP, the agents are arranged as a DFS pseudo-tree. Recently it has been observed that the constructed pseudo-trees in this way often come to be chain-like and greatly impair the algorithm's performance. To address these issues, we develop an algorithm that speeds up the DPOP algorithm by reducing the size of the messages exchanged and increasing parallelism in the pseudo tree. Our empirical evidence suggests that our approach outperforms the state-of-the-art algorithms by a significant margin.

Partitioning a graph using graph separators, and particularly clique separators, are well-known techniques to decompose a graph into smaller units which can be treated independently. It was previously known that the treewidth was bounded above by the sum of the size of the separator plus the treewidth of disjoint components, and this was obtained by the heuristic of filling in all edges of the separator making it into a clique. In this paper, we present a new, tighter upper bound on the treewidth of a graph obtained by only partially filling in the edges of a separator. In particular, the method completes just those pairs of separator vertices that are adjacent to a common component, and indicates a more effective heuristic than filling in the entire separator. We discuss the relevance of this result for combinatorial algorithms and give an example of how the tighter bound can be exploited in the domain of constraint satisfaction problems.

The fixed parameter tractable (FPT) approach is a powerful tool in tackling computationally hard problems.  In this paper, we link FPT results to classic artificial intelligence (AI) techniques to show how they complement each other.  Specifically, we consider the workflow satisfiability problem (WSP) which asks whether there exists an assignment of authorised users to the steps in a workflow specification, subject to certain constraints on the assignment.  It was shown by Cohen et al. (JAIR 2014) that WSP restricted to the class of user-independent constraints (UI), covering many practical cases, admits FPT algorithms, i.e. can be solved in time exponential only in the number of steps k and polynomial in the number of users n.  Since usually k << n in WSP, such FPT algorithms are of great practical interest.We present a new interpretation of the FPT nature of the WSP with UI constraints giving a decomposition of the problem into two levels.  Exploiting this two-level split, we develop a new FPT algorithm that is by many orders of magnitude faster than the previous state-of-the-art WSP algorithm and also has only polynomial-space complexity.  We also introduce new pseudo-Boolean (PB) and Constraint Satisfaction (CSP) formulations of the WSP with UI constraints which efficiently exploit this new decomposition of the problem and raise the novel issue of how to use general-purpose solvers to tackle FPT problems in a fashion that meets FPT efficiency expectations.  In our computational study, we investigate, for the first time, the phase transition (PT) properties of the WSP, under a model for generation of random instances.  We show how PT studies can be extended, in a novel fashion, to support empirical evaluation of scaling of FPT algorithms.

In this work, we aim to utilize prior knowledge encoded as logical rules to improve the performance of deep models. We propose a logic graph embedding network that projects d-DNNF formulae (and assignments) onto a manifold via an augmented Graph Convolutional Network (GCN). To generate semantically-faithful embeddings, we propose techniques to recognize node heterogeneity, and semantic regularization that incorporate structural constraints into the embedding. Experiments show that our approach improves the performance of models trained to perform model-checking and visual relation prediction.

Allen's Interval Algebra constitutes a framework for reasoning about temporal information in a qualitative manner. In particular, it uses intervals, i.e., pairs of endpoints, on the timeline to represent entities corresponding to actions, events, or tasks, and binary relations such as precedes and overlaps to encode the possible configurations between those entities. Allen's calculus has found its way in many academic and industrial applications that involve, most commonly, planning and scheduling, temporal databases, and healthcare. In this paper, we present a novel encoding of Interval Algebra using answer-set programming (ASP) extended by difference constraints, i.e., the fragment abbreviated as ASP(DL), and demonstrate its performance via a preliminary experimental evaluation. Although our ASP encoding is presented in the case of Allen's calculus for the sake of clarity, we suggest that analogous encodings can be devised for other point-based calculi, too.