In this paper, we show how model-checking can be generalized to temporal logic constraint solving, by considering temporal logic formulae with free variables over some domain D, and by computing a validity domain for ...
详细信息
ISBN:
(纸本)9783642042430
In this paper, we show how model-checking can be generalized to temporal logic constraint solving, by considering temporal logic formulae with free variables over some domain D, and by computing a validity domain for the variables rather than a truth value for the formula. this allows us to define a continuous degree of satisfaction for a temporal logic formula ill a, given structure, opening up the field of model-checking to optimization. We illustrate this approach with reverse engineering problems coming from systems biology, and provide some performance figures oil parameter optimization problems with respect to temporal logic specifications.
ABT is the reference algorithm for asynchronous distributed constraint satisfaction. When searching, ABT produces nogoods as justifications of deleted values. When one of such nogoods has an empty left-hand side, the ...
详细信息
ISBN:
(纸本)9783540859574
ABT is the reference algorithm for asynchronous distributed constraint satisfaction. When searching, ABT produces nogoods as justifications of deleted values. When one of such nogoods has an empty left-hand side, the considered value is eliminated unconditionally, once and for all. this value deletion can be propagated using standard arc consistency techniques, producing new deletions in the domains of other variables. this causes substantial reductions in the search effort required to solve a class of problems. We also extend this idea to the propagation of conditional deletions. something already proposed in the past. We provide experimental results that show the benefits of the proposed approach, especially considering communication cost.
Distributed computing is increasingly important at a time when the doubling of the number of transistors on a processor every 18 months no longer translates in a doubling of speed but instead a doubling of the number ...
详细信息
ISBN:
(纸本)3540462678
Distributed computing is increasingly important at a time when the doubling of the number of transistors on a processor every 18 months no longer translates in a doubling of speed but instead a doubling of the number of cores. Unfortunately, it also places significant conceptual and implementation burden on programmers. this paper aims at addressing this challenge for constraint-based local search (CBLS), whose search procedures typically exhibit inherent parallelism stemming from multistart, restart, or population-based techniques whose benefits have been demonstrated both experimentally and theoretically. the,paper presents abstractions that allows distributed CBLS programs to be close to their sequential and parallel counterparts, keeping the conceptual and implementation overhead of distributed computing minimal. A preliminary implementation in COMET exhibits significant speed-ups in constraint satisfaction and optimization applications. the implementation also scales well withthe number of machines. Of particular interest is the observation that generic abstractions of CBLS and cp, such as models and solutions, and advanced control structures such as events and closures, play a fundamental role to keep the distance between sequential and distributed CBLS programs small. As a result, the abstractions directly apply to cp programs using multistarts or restarts procedures.
the heavy-tailed phenomenon that characterises the runtime distributions of backtrack search procedures has received considerable attention over the past few years. Some have conjectured that heavy-tailed behaviour is...
详细信息
ISBN:
(纸本)3540292381
the heavy-tailed phenomenon that characterises the runtime distributions of backtrack search procedures has received considerable attention over the past few years. Some have conjectured that heavy-tailed behaviour is largely due to the characteristics of the algorithm used. Others have conjectured that problem structure is a significant contributor. In this paper we attempt to explore the former hypothesis, namely we study how variable and value ordering heuristics impact the heavy-tailedness of runtime distributions of backtrack search procedures. We demonstrate that heavy-tailed behaviour can be eliminated from particular classes of random problems by carefully selecting the search heuristics, even when using chronological backtrack search. We also show that combinations of good search heuristics can eliminate heavy tails from Quasigroups with Holes of order 10, and give some insights into why this is the case. these results motivate a more detailed analysis of the effects that variable and value ordering can have on heavy-tailedness. We show how combinations of variable and value ordering heuristics can result in a runtime distribution being inherently heavytailed. Specifically, we show that even if we were to use an Oracle to refute insoluble subtrees optimally, for some combinations of heuristics we would still observe heavy-tailed behaviour. Finally, we study the distributions of refutation sizes found using different combinations of heuristics and gain some further insights into what characteristics tend to give rise to heavy-tailed behaviour.
the paper introduces the notion of freely completable partial solutions to characterize constraint satisfaction problems that have components which are relatively easy to solve and are only loosely connected to the re...
详细信息
ISBN:
(纸本)3540232419
the paper introduces the notion of freely completable partial solutions to characterize constraint satisfaction problems that have components which are relatively easy to solve and are only loosely connected to the remaining parts of the problem. Discovering such partial solutions during the solution process can result in strongly pruned search trees. We give a general definition of freely completable partial solutions, and then apply it to resource-constrained project scheduling. In this domain, we suggest a heuristic algorithm that is able to construct freely completable partial schedules. the method – together with symmetry breaking applied before search – has been successfully tested on real-life resource-constrained project scheduling problems containing up to 2000 tasks.
作者：
Golden, KPang, WLNASA
Ames Res Ctr Computat Sci Div Moffett Field CA 94035 USA NASA
Ames Res Ctr QSS Grp Inc Moffett Field CA 94035 USA
this paper discusses an approach to representing and reasoning about constraints over strings. We discuss how string domains can often be concisely represented using regular languages, and how constraints over strings...
详细信息
ISBN:
(纸本)3540202021
this paper discusses an approach to representing and reasoning about constraints over strings. We discuss how string domains can often be concisely represented using regular languages, and how constraints over strings, and domain operations on sets of strings, can be carried out using this representation.
this paper develops a secure distributed constraint Satisfaction algorithm. A Distributed constraint Satisfaction Problem (DisCSP) is a CSP in which variables and constraints are distributed among multiple agents. A m...
详细信息
We first present a generic pruning technique which aggregates several constraints sharing some variables. the method is derived from an idea called sweep which is extensively used in computational geometry. A first be...
详细信息
暂无评论