constraint satisfaction and propositional satisfiability problems are often solved using backtracking search. Previous studies have shown that a technique called randomization and restarts can dramatically improve, th...
详细信息
ISBN:
(纸本)9783540749691
constraint satisfaction and propositional satisfiability problems are often solved using backtracking search. Previous studies have shown that a technique called randomization and restarts can dramatically improve, the performance of a, backtracking algorithm on some instances. We consider the commonly occurring scenario where one is to solve an ensemble of instances using a backtracking algorithm and wish to learn a good restart strategy for the ensemble. In contrast to much previous work, our focus is on universal strategies. We contribute to the theoretical understanding of universal strategies and demonstrate both analytically and empirically the pitfalls of non-universal strategies. We also propose a simple approach for learning good universal restart strategies and demonstrate the effectiveness and robustness of our approach through an extensive empirical evaluation on a real-world testbed.
We propose two new asynchronous algorithms for solving Distributed constraint Satisfaction Problems (DisCSPs). the first algorithm, AFC-ng, is a nogood-based version of Asynchronous Forward Checking (AFC). the second ...
详细信息
ISBN:
(纸本)9783642042430
We propose two new asynchronous algorithms for solving Distributed constraint Satisfaction Problems (DisCSPs). the first algorithm, AFC-ng, is a nogood-based version of Asynchronous Forward Checking (AFC). the second algorithm, Asynchronous Inter-Level Forward-Checking (AILFC), is based oil the AFC-ng algorithm and is performed oil a pseudo-tree ordering of the constraint graph. AFC-ng and AILFC only need polynomial space. We compare the performance of these algorithms with other DisCSP algorithms on random DisCSPs in two kinds of communication environments: Fast communication and slow communication. Our experiment,, show that AFC-ng improves oil AFC and that AILFC Outperforms all compared algorithms in communication load.
We introduce a constraint-based framework for studying infinite qualitative simulations concerned with contingencies such as time, space, shape, size, abstracted into a finite set of qualitative relations. To define t...
详细信息
ISBN:
(纸本)3540462678
We introduce a constraint-based framework for studying infinite qualitative simulations concerned with contingencies such as time, space, shape, size, abstracted into a finite set of qualitative relations. To define the simulations we combine constraints that formalize the background knowledge concerned with qualitative reasoning with appropriate inter-state constraints that are formulated using linear temporal logic. We implemented this approach in a constraintprogramming system ((ECLPSe)-P-i) by drawing on the ideas from bounded model checking. the implementation became realistic only after several rounds of optimizations and experimentation with various heuristics. the resulting system allows us to test and modify the problem specifications in a straightforward way and to combine various knowledge aspects. To demonstrate the expressiveness and simplicity of this approach we discuss in detail two examples: a navigation problem and a simulation of juggling.
Visualization is often invaluable to understand the behavior of optimization algorithms, identify their bottlenecks or pathological behaviors, and suggest remedial techniques. Yet developing visualizations is often a ...
详细信息
Visualization is often invaluable to understand the behavior of optimization algorithms, identify their bottlenecks or pathological behaviors, and suggest remedial techniques. Yet developing visualizations is often a tedious activity requiring significant time and expertise. this paper presents a framework for the visualization of constraint-based local search (CBLS) algorithms. Given a high-level model and a declarative visualization specification, the CBLS visualizer systematically produces animations to visualize constraints and objectives, violations, and conflicts, as well as the temporal behavior of these measures. the visualization specification is declarative and typically composed of a triple (what,where,how) indicating what to display, where, and with which graphical objects. the visualizer architecture is compositional and extensible. It provides building blocks which can be assembled freely by the user and focuses almost exclusively on static aspects, the dynamic aspects being automated by the use of invariants. the paper highlights various functionalities of the visualizer and describes a blueprint for its implementation.
We introduce the SOFTALLEQUAL global constraint. which maximizes the number of equalities holding between hairs of assignments to a set of variables. MO study the computational complexity of propagating this constrain...
详细信息
ISBN:
(纸本)9783540859574
We introduce the SOFTALLEQUAL global constraint. which maximizes the number of equalities holding between hairs of assignments to a set of variables. MO study the computational complexity of propagating this constraint, showing that it is intractable in general. Since maximizing the number of pairs of equally assigned variables ill a set is NP-hard. We propose three: ways of coping with NP-hardness Firstly, we develop a greedy linear-time algorithm to approximate the maximum number of equalities within a factor on. Secondly. we identify a tractable (polynomial) class for this constraint. thirdly;we identify a parameter based oil this class and show that the SOFTALLEQUAL constraint is fixed-parameter tractable with respect to this parameter.
constraint solvers are complex pieces of software and are notoriously difficult to debug. In large part this is due to the difficulty of pinpointing the source of an error in the vast searches these solvers perform, s...
详细信息
ISBN:
(数字)9783319983349
ISBN:
(纸本)9783319983349;9783319983332
constraint solvers are complex pieces of software and are notoriously difficult to debug. In large part this is due to the difficulty of pinpointing the source of an error in the vast searches these solvers perform, since the effect of an error may only come to light long after the error is made. In addition, an error does not necessarily lead to the wrong result, further complicating the debugging process. A major source of errors in a constraint solver is the complex constraint propagation algorithms that provide the inference that controls and directs the search. In this paper we show that metamorphic testing is a principled way to test constraint solvers by comparing two different implementations of the same constraint. Specifically, specialised propagators for the constraint are tested against the general purpose table constraint propagator. We report on metamorphic testing of the constraint solver Minion. We demonstrate that the metamorphic testing method is very effective for finding artificial bugs introduced by random code mutation.
Tractability results for structural subproblems have generally been considered for explicit relations listing the allowed assignments. In this paper we define a representation which allows us to express constraint rel...
详细信息
ISBN:
(纸本)3540462678
Tractability results for structural subproblems have generally been considered for explicit relations listing the allowed assignments. In this paper we define a representation which allows us to express constraint relations as either an explicit set of allowed labelings, or an explicit set of disallowed labelings, whichever is smaller. We demonstrate a new structural width parameter, which we call the interaction width, that when bounded allows us to carry over well known structural decompositions to this more concise representation. Our results naturally derive new structurally tractable classes for SAT.
this paper describes a new approach for solving disjunctive temporal problems such as the open shop and job shop scheduling domains. Much previous research in systematic search approaches for these problems has focuse...
详细信息
ISBN:
(纸本)9783642042430
this paper describes a new approach for solving disjunctive temporal problems such as the open shop and job shop scheduling domains. Much previous research in systematic search approaches for these problems has focused oil developing problem specific constraint propagators and ordering heuristics. Indeed, the common belief is that many of these problems are too difficult to solve without such domain specific models. We introduce a simple constraint model that combines a generic adaptive heuristic with naive propagation, and show that it often outperforms state-of-the-art solvers for both open shop and job shop problems.
Multi-core processors require programmers to exploit concurrency in software as far as possible. Unfortunately, our current concurrency abstractions make multi-core programming harder than necessary because we have to...
详细信息
the class of constraint satisfaction problems (CSPs) over finite domains has been shown to be NP-complete, but many tractable subclasses have been identified in the literature. In this paper we are interested in restr...
详细信息
ISBN:
(纸本)3540666265
the class of constraint satisfaction problems (CSPs) over finite domains has been shown to be NP-complete, but many tractable subclasses have been identified in the literature. In this paper we are interested in restrictions on the types of constraint relations in CSP instances. By a result of Jeavons et al. we know that a key to the complexity of classes arising from such restrictions is the closure properties of the sets of relations. It has been shown that sets of relations that are closed under constant, majority, affine, or associative, commutative, and idempotent (ACI) functions yield tractable subclasses of CSP. However, it has been unknown whether other closure properties may generate tractable subclasses. In this paper we introduce a class of tractable (in fact, SL-complete) CSPs based on bipartite graphs. We show that there are members of this class that are not closed under constant, majority, affine, or ACI functions, and that it, therefore, is incomparable with previously identified classes.
暂无评论