The Experts below are selected from a list of 37431 Experts worldwide ranked by ideXlab platform
Markus Triska - One of the best experts on this subject based on the ideXlab platform.
-
the finite Domain Constraint solver of swi prolog
International Symposium on Functional and Logic Programming, 2012Co-Authors: Markus TriskaAbstract:We present a new Constraint solver over finite Domains, freely available as library(clpfd) in SWI-Prolog. Our solver has several unique features, which we describe in this paper: Reasoning over arbitrarily large integers, always terminating propagation, and a Domain-specific language that concisely expresses the full semantics of Constraint reification. The library is entirely written in Prolog and can be easily ported to other Prolog systems that support attributed variables. The Constraint solver is fast enough for teaching and research purposes and is already being used in courses at several universities in France, Germany, Italy, Austria and other countries.
-
Domain-specific Languages in a Finite Domain Constraint Programming System
arXiv: Artificial Intelligence, 2011Co-Authors: Markus TriskaAbstract:In this paper, we present Domain-specific languages (DSLs) that we devised for their use in the implementation of a finite Domain Constraint programming system, available as library(clpfd) in SWI-Prolog and YAP-Prolog. These DSLs are used in propagator selection and Constraint reification. In these areas, they lead to concise specifications that are easy to read and reason about. At compilation time, these specifications are translated to Prolog code, reducing interpretative run-time overheads. The devised languages can be used in the implementation of other finite Domain Constraint solvers as well and may contribute to their correctness, conciseness and efficiency.
-
A generalised finite Domain Constraint solver for SWI-Prolog
CTIT technical reports series, 2008Co-Authors: Markus Triska, Ulrich Neumerkel, Jan WielemakerAbstract:In this paper we describe a new Constraint solver over finite Domains that has recently been included in the SWI-Prolog distribution 1. Our solver generalises finite Domain Constraint solving towards unbounded Domains, and thus enables a uniform approach to integer arithmetic and Constraints. We ensure termination of all predicates, which facilitates termination proofs of Constraint logic programs. The solver is written in Prolog and can be quite easily ported to other systems.
Peter J. Stuckey - One of the best experts on this subject based on the ideXlab platform.
-
SAC - Constraint propagation for loose Constraint graphs
Proceedings of the 2007 ACM symposium on Applied computing - SAC '07, 2007Co-Authors: Kathryn Francis, Peter J. StuckeyAbstract:In this paper we investigate how to improve propagation-based finite Domain Constraint solving by making use of the Constraint graph to choose propagators to execute in a better order. If the Constraint graph is not too densely connected we can build an underlying tree of bi-connected components, and use this to order the choice of propagator. Our experiments show that there exist problems where handling biconnected components can substantially improve the propagation performance.
-
a hybrid bdd and sat finite Domain Constraint solver
Practical Aspects of Declarative Languages, 2006Co-Authors: Peter Hawkins, Peter J. StuckeyAbstract:Finite-Domain Constraint solvers based on Binary Decision Diagrams (BDDs) are a powerful technique for solving Constraint problems over finite set and integer variables represented as Boolean formulae. Boolean Satisfiability (SAT) solvers are another form of Constraint solver that operate on Constraints on Boolean variables expressed in clausal form. Modern SAT solvers have highly optimized propagation mechanisms and also incorporate efficient conflict-clause learning algorithms and effective search heuristics based on variable activity, but these techniques have not been widely used in finite-Domain solvers. In this paper we show how to construct a hybrid BDD and SAT solver which inherits the advantages of both solvers simultaneously. The hybrid solver makes use of an efficient algorithm for capturing the inferences of a finite-Domain Constraint solver in clausal form, allowing us to automatically and transparently construct a SAT model of a finite-Domain Constraint problem. Finally, we present experimental results demonstrating that the hybrid solver can outperform both SAT and finite-Domain solvers by a substantial margin.
-
PADL - A hybrid BDD and SAT finite Domain Constraint solver
Practical Aspects of Declarative Languages, 2005Co-Authors: Peter Hawkins, Peter J. StuckeyAbstract:Finite-Domain Constraint solvers based on Binary Decision Diagrams (BDDs) are a powerful technique for solving Constraint problems over finite set and integer variables represented as Boolean formulae. Boolean Satisfiability (SAT) solvers are another form of Constraint solver that operate on Constraints on Boolean variables expressed in clausal form. Modern SAT solvers have highly optimized propagation mechanisms and also incorporate efficient conflict-clause learning algorithms and effective search heuristics based on variable activity, but these techniques have not been widely used in finite-Domain solvers. In this paper we show how to construct a hybrid BDD and SAT solver which inherits the advantages of both solvers simultaneously. The hybrid solver makes use of an efficient algorithm for capturing the inferences of a finite-Domain Constraint solver in clausal form, allowing us to automatically and transparently construct a SAT model of a finite-Domain Constraint problem. Finally, we present experimental results demonstrating that the hybrid solver can outperform both SAT and finite-Domain solvers by a substantial margin.
Mats Carlsson - One of the best experts on this subject based on the ideXlab platform.
-
Handbook of Constraint Programming - Finite Domain Constraint programming systems
Handbook of Constraint Programming, 2006Co-Authors: Christian Schulte, Mats CarlssonAbstract:Publisher Summary This chapter focuses on the propagation-based finite Domain Constraint programming systems—that is, systems that solve problems using Constraint propagation involving variables ranging over some finite set of integers. The focus on finite Domain Constraint programming systems coincides with both practical relevance and known principles and techniques: systems at least offer services for finite Domains; much of the known principles and techniques are conceived and documented for finite Domains. The chapter! concludes that finite-Domain Constraint programming systems are proved to be useful tools for solving many problems in a wide range of application areas. Several useful techniques for the implementation of Constraint systems are available, both for Constraint propagation as well as for search. However, because of the change of available hardware platforms, the advent of new methods for problem solving and new Constraints and propagators, and new requirements for systems, it is clear that the development of Constraint programming systems will be faced with many new and difficult challenges.
-
finite Domain Constraint programming systems
Foundations of Artificial Intelligence, 2006Co-Authors: Christian Schulte, Mats CarlssonAbstract:Publisher Summary This chapter focuses on the propagation-based finite Domain Constraint programming systems—that is, systems that solve problems using Constraint propagation involving variables ranging over some finite set of integers. The focus on finite Domain Constraint programming systems coincides with both practical relevance and known principles and techniques: systems at least offer services for finite Domains; much of the known principles and techniques are conceived and documented for finite Domains. The chapter! concludes that finite-Domain Constraint programming systems are proved to be useful tools for solving many problems in a wide range of application areas. Several useful techniques for the implementation of Constraint systems are available, both for Constraint propagation as well as for search. However, because of the change of available hardware platforms, the advent of new methods for problem solving and new Constraints and propagators, and new requirements for systems, it is clear that the development of Constraint programming systems will be faced with many new and difficult challenges.
-
an open ended finite Domain Constraint solver
International Symposium on Programming Language Implementation and Logic Programming, 1997Co-Authors: Mats Carlsson, Greger Ottosson, Björn CarlsonAbstract:We describe the design and implementation of a finite Domain Constraint solver embedded in a Prolog system using an extended unification mechanism via attributed variables as a generic Constraint interface. The solver is essentially a scheduler for indexicals, i.e. reactive functional rules encoding local consistency methods performing incremental Constraint solving or entailment checking, and global Constraints, i.e. general propagators which may use specialized algorithms to achieve a higher degree of consistency or better time and space complexity.
-
PLILP - An Open-Ended Finite Domain Constraint Solver
Lecture Notes in Computer Science, 1997Co-Authors: Mats Carlsson, Greger Ottosson, Björn CarlsonAbstract:We describe the design and implementation of a finite Domain Constraint solver embedded in a Prolog system using an extended unification mechanism via attributed variables as a generic Constraint interface. The solver is essentially a scheduler for indexicals, i.e. reactive functional rules encoding local consistency methods performing incremental Constraint solving or entailment checking, and global Constraints, i.e. general propagators which may use specialized algorithms to achieve a higher degree of consistency or better time and space complexity.
-
CP - Towards an open finite Domain Constraint solver
Lecture Notes in Computer Science, 1996Co-Authors: Mats Carlsson, Björn Carlson, Greger OttossonAbstract:We describe the design and implementation of a finite Domain Constraint solver embedded in SICStus Prolog system using an extended unification mechanism via attributed variables as a generic Constraint interface. The solver is based on indexicals, i.e. reactive functional rules performing incremental Constraint solving or entailment checking. Propagation is done using the arc-consistency algorithm AC-3, adapted for non-binary Constraints. At the heart of the algorithm is an evaluator for indexicals. The solver provides the usual predefined search strategies (fixed order, failfirst principle, branch and bound for minimization or maximization). Access predicates for the relevant variable attributes (Domain value, bounds and size etc.) are also provided, making customized search strategies easily programmable. A design goal has been to keep the solver open-ended and extendible as well as to keep a substantial part written in Prolog, partly contradicting conventional wisdom in implementing Constraint solvers.
Peter Hawkins - One of the best experts on this subject based on the ideXlab platform.
-
a hybrid bdd and sat finite Domain Constraint solver
Practical Aspects of Declarative Languages, 2006Co-Authors: Peter Hawkins, Peter J. StuckeyAbstract:Finite-Domain Constraint solvers based on Binary Decision Diagrams (BDDs) are a powerful technique for solving Constraint problems over finite set and integer variables represented as Boolean formulae. Boolean Satisfiability (SAT) solvers are another form of Constraint solver that operate on Constraints on Boolean variables expressed in clausal form. Modern SAT solvers have highly optimized propagation mechanisms and also incorporate efficient conflict-clause learning algorithms and effective search heuristics based on variable activity, but these techniques have not been widely used in finite-Domain solvers. In this paper we show how to construct a hybrid BDD and SAT solver which inherits the advantages of both solvers simultaneously. The hybrid solver makes use of an efficient algorithm for capturing the inferences of a finite-Domain Constraint solver in clausal form, allowing us to automatically and transparently construct a SAT model of a finite-Domain Constraint problem. Finally, we present experimental results demonstrating that the hybrid solver can outperform both SAT and finite-Domain solvers by a substantial margin.
-
PADL - A hybrid BDD and SAT finite Domain Constraint solver
Practical Aspects of Declarative Languages, 2005Co-Authors: Peter Hawkins, Peter J. StuckeyAbstract:Finite-Domain Constraint solvers based on Binary Decision Diagrams (BDDs) are a powerful technique for solving Constraint problems over finite set and integer variables represented as Boolean formulae. Boolean Satisfiability (SAT) solvers are another form of Constraint solver that operate on Constraints on Boolean variables expressed in clausal form. Modern SAT solvers have highly optimized propagation mechanisms and also incorporate efficient conflict-clause learning algorithms and effective search heuristics based on variable activity, but these techniques have not been widely used in finite-Domain solvers. In this paper we show how to construct a hybrid BDD and SAT solver which inherits the advantages of both solvers simultaneously. The hybrid solver makes use of an efficient algorithm for capturing the inferences of a finite-Domain Constraint solver in clausal form, allowing us to automatically and transparently construct a SAT model of a finite-Domain Constraint problem. Finally, we present experimental results demonstrating that the hybrid solver can outperform both SAT and finite-Domain solvers by a substantial margin.
Peter Jonsson - One of the best experts on this subject based on the ideXlab platform.
-
An initial study of time complexity in infinite-Domain Constraint satisfaction
Artificial Intelligence, 2017Co-Authors: Peter Jonsson, Victor LagerkvistAbstract:Abstract The Constraint satisfaction problem (CSP) is a widely studied problem with numerous applications in computer science and artificial intelligence. For infinite-Domain CSPs, there are many results separating tractable and NP-hard cases while upper and lower bounds on the time complexity of hard cases are virtually unexplored. Hence, we initiate a study of the worst-case time complexity of such CSPs. We analyze backtracking algorithms and determine upper bounds on their time complexity. We present asymptotically faster algorithms based on enumeration techniques and we show that these algorithms are applicable to well-studied problems in, for instance, temporal reasoning. Finally, we prove non-trivial lower bounds applicable to many interesting CSPs, under the assumption that certain complexity-theoretic assumptions hold. The gap between upper and lower bounds is in many cases surprisingly small, which suggests that our upper bounds cannot be significantly improved.
-
MFCS - Finite Domain Constraint Satisfaction Using Quantum Computation
Lecture Notes in Computer Science, 2002Co-Authors: Ola Angelsmark, Vilhelm Dahllöf, Peter JonssonAbstract:We present a quantum algorithm for finite Domain Constraint solving, where the Constraints have arity 2. It is complete and runs in O((?d/2?)n/2) time, where d is size of the Domain of the variables and n the number of variables. For the case of d = 3we provide a method to obtain an upper time bound of O(8n/8)? O(1.2968n). Also for d = 5 the upper bound has been improved. Using this method in a slightly different way we can decide 3-colourability in O(1.2185n) time.