In constraint Satisfaction, basic inferences rely oil some properties of constraint networks, called consistencies, that allow the identification of inconsistent instantiations (also called nogoods). Two main families...
详细信息
ISBN:
(纸本)9783642042430
In constraint Satisfaction, basic inferences rely oil some properties of constraint networks, called consistencies, that allow the identification of inconsistent instantiations (also called nogoods). Two main families of consistencies have been introduced so far: those that permit LIS to reason from variables Such as (i, j)-consistency and those that permit us to reason from constraints Such as relational (i, j)-consistency. this paper introduces a new family of consistencies based on the concept of flailed value (a value pruned during search). this family is orthogonal to previous ones.
the timed concurrent constraint language (tccp in short) is a concurrent logic language based on the simple but powerful concurrent constraint paradigm of Saraswat. In this paradigm, the notion of store-as-value is re...
详细信息
the timed concurrent constraint language (tccp in short) is a concurrent logic language based on the simple but powerful concurrent constraint paradigm of Saraswat. In this paradigm, the notion of store-as-value is replaced by the notion of store-as-constraint, which introduces some differences w.r.t. other approaches to concurrency. In this paper, we provide a general framework for the debugging of tccp programs. To this end, we first present a new compact, bottom-up semantics for the language that is well suited for debugging and verification purposes in the context of reactive systems. We also provide an abstract semantics that allows us to effectively implement debugging algorithms based on abstract interpretation. Given a tccp program and a behavior specification, our debugging approach automatically detects whether the program satisfies the specification. this differs from other semi-automatic approaches to debugging and avoids the need to provide symptoms in advance. We show the efficacy of our approach by introducing two illustrative examples. We choose a specific abstract domain and show how we can detect that a program is erroneous.
In this paper, we present a major improvement in the search procedures in constraintprogramming. First, we integrate various search procedures from Al and OR. Second, we parallelize the search on shared-memory comput...
详细信息
ISBN:
(纸本)3540666265
In this paper, we present a major improvement in the search procedures in constraintprogramming. First, we integrate various search procedures from Al and OR. Second, we parallelize the search on shared-memory computers. third, we add an object-oriented extensible control language to implement complex complete and incomplete search procedures. the result is a powerful set of tools which offers both brute force search using simple search procedures and parallelism, and finely tuned search procedures using that expressive control language. Withthis, we were able both to solve difficult and open problems using complete search procedures, and to quickly produce good results using incomplete search procedures.
One promising trend in digital system integration consists of boosting on-chip communication performance by means of silicon photonics, thus materializing the so-called Optical Networkson- Chip. Among them, wavelength...
详细信息
One promising trend in digital system integration consists of boosting on-chip communication performance by means of silicon photonics, thus materializing the so-called Optical Networkson- Chip. Among them, wavelength routing can be used to route a signal to destination by univocally associating a routing path to the wavelength of the optical carrier. Such wavelengths should be chosen so to minimize interferences among optical channels and to avoid routing faults. As a result, physical parameter selection of such networks requires the solution of complex constrained optimization problems. In previous work, published in the proceedings of the internationalconference on Computer-Aided Design, we proposed and solved the problem of computing the maximum parallelism obtainable in the communication between any two endpoints while avoiding misrouting of optical signals. the underlying technology, only quickly mentioned in that paper, is Answer Set programming. In this work, we detail the Answer Set programming approach we used to solve such problem. Another important design issue is to select the wavelengths of optical carriers such that they are spread across the available spectrum, in order to reduce the likelihood that, due to imperfections in the manufacturing process, unintended routing faults arise. We show how to address such problem in constraint Logic programming on Finite Domains.
Bounded Max-Sum is a message-passing algorithm for solving Distributed constraint Optimization Problems (DCOP) able to compute solutions with a guaranteed approximation ratio. In this paper we show that the introducti...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
Bounded Max-Sum is a message-passing algorithm for solving Distributed constraint Optimization Problems (DCOP) able to compute solutions with a guaranteed approximation ratio. In this paper we show that the introduction of an intermediate step that decomposes functions may significantly improve its accuracy. this is especially relevant in critical applications (e. g. automatic surveillance, disaster response scenarios) where the accuracy of solutions is of vital importance.
this paper presents a technique for learning parameterized implied constraints. they can be added to a model to improve the solving process. Experiments on implied Gcc constraints show the interest of our approach.
ISBN:
(纸本)3540292381
this paper presents a technique for learning parameterized implied constraints. they can be added to a model to improve the solving process. Experiments on implied Gcc constraints show the interest of our approach.
Local Consistency has proven to be an important notion in the study of constraint satisfaction problems. We give an algebraic condition that characterizes all the constraint types for which generalized are-consistency...
详细信息
ISBN:
(纸本)3540666265
Local Consistency has proven to be an important notion in the study of constraint satisfaction problems. We give an algebraic condition that characterizes all the constraint types for which generalized are-consistency is sufficient to ensure the existence of a solution. We give some examples to illustrate the application of this result.
In CP literature combinatorial design problems such as sport scheduling, Steiner systems, error-correcting codes and more, are typically solved using Finite Domain (FD) models despite often being more naturally expres...
详细信息
ISBN:
(纸本)3540232419
In CP literature combinatorial design problems such as sport scheduling, Steiner systems, error-correcting codes and more, are typically solved using Finite Domain (FD) models despite often being more naturally expressed as Finite Set (FS) models. Existing FS solvers have difficulty with such problems as they do not make strong use of the ubiquitous set cardinality information. We investigate a new approach to strengthen the propagation of FS constraints in a tractable way: extending the domain representation to more closely approximate the true domain of a set variable. We show how this approach allows us to reach a stronger level of consistency, compared to standard FS solvers, for arbitrary constraints as well as providing a mechanism for implementing certain symmetry breaking constraints. By experiments on Steiner Systems and error correcting codes, we demonstrate that our approach is not only an improvement over standard FS solvers but also an improvement on recently published results using FD 0/1 matrix models as well.
String processing is ubiquitous across computer science, and arguably more so in web programming. In order to reason about programs manipulating strings we need to solve constraints over strings. In constraint Program...
详细信息
ISBN:
(纸本)9783319661582;9783319661575
String processing is ubiquitous across computer science, and arguably more so in web programming. In order to reason about programs manipulating strings we need to solve constraints over strings. In constraintprogramming, the only approaches we are aware for representing string variables-having bounded yet possibly unknown size-degrade when the maximum possible string length becomes too large. In this paper, we introduce a novel approach that decouples the size of the string representation from its maximum length. the domain of a string variable is dynamically represented by a simplified regular expression that we called a dashed string, and the constraint solving relies on propagation of information based on equations between dashed strings. We implemented this approach in G-Strings, a new string solver-built on top of Gecode solver-that already shows some promising results.
Great progress has been made on DPLL based SAT solvers operating on CNF encoded SAT theories. However, for most problems CNF is not a very natural representation. Typically these problems are more easily expressed usi...
详细信息
ISBN:
(纸本)3540232419
Great progress has been made on DPLL based SAT solvers operating on CNF encoded SAT theories. However, for most problems CNF is not a very natural representation. Typically these problems are more easily expressed using unrestricted propositional formulae and hence must be converted to CNF before modem SAT solvers can be applied. this conversion entails a considerable loss of information about the problem's structure. In this work we demonstrate that conversion to CNF is both unnecessary and undesirable. In particular, we demonstrate that a SAT solver which operates directly on a propositional formula can achieve the same efficiency as a highly optimized modern CNF solver. Furthermore, since the original formula remains intact, such a solver can exploit the original problem structure to improve over CNF solvers. We present empirical evidence showing that exploiting the original structure can yield considerable benefits.
暂无评论