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.
the Java JDK security model provides an access control mechanism for the JVM based on dynamic stack inspection. Previous results have shown how stack inspection can be enforced at compile time via whole-program type a...
详细信息
this paper proposes the design and implementation of a dynamic programming based algorithm for (distributed) constraint optimization, which exploits modern massively parallel architectures, such as those found in mode...
详细信息
ISBN:
(纸本)9783319232195;9783319232188
this paper proposes the design and implementation of a dynamic programming based algorithm for (distributed) constraint optimization, which exploits modern massively parallel architectures, such as those found in modern Graphical Processing Units (GPUs). the paper studies the proposed algorithm in both centralized and distributed optimization contexts. the experimental analysis, performed on unstructured and structured graphs, shows the advantages of employing GPUs, resulting in enhanced performances and scalability.
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.
this paper describes a systematic method for deriving efficient algorithms and precise time complexities from extended Datalog rules as it is applied to the analysis of trust management policies specified in SPKI/SDSI...
详细信息
the propositional satisfiability problem (SAT) is one of the simplest instances of constraintprogramming (CP): variables are bi-valued (can only take values 0 or 1), and all constraints are clauses (disjunctions of l...
详细信息
暂无评论