Accurately estimating the distribution of solutions to a problem, should such solutions exist, provides efficient search heuristics. the purpose of this paper is to propose new ways of computing such estimates, with d...
详细信息
ISBN:
(纸本)9783642042430
Accurately estimating the distribution of solutions to a problem, should such solutions exist, provides efficient search heuristics. the purpose of this paper is to propose new ways of computing such estimates, with different degrees of accuracy and complexity. We build oil the Expectation-Maximizatiou Belief-Propagation (EMPB) framework proposed by Hsu et al. to solve constraint Satisfaction Problems (CSPs). We propose two general approaches within the EMBP framework: we firstly derive update rules at;the constraint level while enforcing domain consistency and then derive update rules globally, at the problem level. the contribution of this paper is two-fold: first, we derive new generic update rules suited to tackle ally CSP;second, we propose all efficient EMP-inspired approach, thereby improving this method and making it competitive withthe state of the art. We evaluate these approaches experimentally and demonstrate their effectiveness.
Ideally, programming propagators as implementations of constraints should be an entirely declarative specification process for a large class of constraints: a high-level declarative specification is automatically tran...
详细信息
ISBN:
(纸本)3540462678
Ideally, programming propagators as implementations of constraints should be an entirely declarative specification process for a large class of constraints: a high-level declarative specification is automatically translated into an efficient propagator. this paper introduces the use of existential monadic second-order logic as declarative specification language for finite set propagators. the approach taken in the paper is to automatically derive projection propagators (involving a single variable only) implementing constraints described by formulas. By this, the paper transfers the ideas of indexicals to finite set constraints while considerably increasing the level of abstraction available with indexicals. the paper proves soundness and completeness of the derived propagators and presents a run-time analysis, including techniques for efficiently executing projectors for n-ary constraints.
Dual Consistency (DC) is a property of constraint Networks (CNs) which is equivalent, in its unrestricted form, to Path Consistency (PC). the principle is to perform successive singleton checks (i.e. enforcing arc con...
详细信息
ISBN:
(纸本)9783540749691
Dual Consistency (DC) is a property of constraint Networks (CNs) which is equivalent, in its unrestricted form, to Path Consistency (PC). the principle is to perform successive singleton checks (i.e. enforcing arc consistency after the assignment of a value to a variable) in order to identify inconsistent pairs of values, until a fixpoint is reached. In this paper, we propose two new algorithms, denoted by sDC2 and sDC3, to enforce (strong) PC following the DC approach. these algorithms can be seen as refinements of Mac Gregor's algorithm as they partially and totally exploit the incrementality of the underlying Arc Consistency algorithm. While sDC3 admits the same interesting worst-case complexities as PC8, sDC2 appears to be the most robust algorithm in practice. Indeed, compared to PC8 and the optimal PC2001, sDC2 is usually around one order of magnitude faster on large instances.
Relational consistency algorithms are instrumental for solving difficult instances of constraint Satisfaction Problems (CSPs), often allowing backtrack-free search. In this paper, we improve an algorithm for enforcing...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
Relational consistency algorithms are instrumental for solving difficult instances of constraint Satisfaction Problems (CSPs), often allowing backtrack-free search. In this paper, we improve an algorithm for enforcing relational consistency by exploiting the property that the constraints of the dual encoding of a CSP are piecewise functional. this property allows us to partition a CSP relation into blocks of equivalent tuples at varying levels of granularity. Our new algorithm dynamically exploits those partitions. Our experiments show a significant improvement of the processing time for enforcing relational consistency.
We define a model for heuristic tree search which assumes that the quality of the heuristic used for ordering the successors of a node improves as depth increases. We show that a usual value ordering heuristic for sol...
详细信息
ISBN:
(纸本)3540666265
We define a model for heuristic tree search which assumes that the quality of the heuristic used for ordering the successors of a node improves as depth increases. We show that a usual value ordering heuristic for solving constraint satisfaction problems fits to this model. Our model defines a partial order on the leaf nodes of the search tree, according to their probability to be a solution. We check which search strategies among interleaved depth-first search (IDFS), limited discrepancy search (LDS) and depth-bounded discrepancy search (DDS) visit the leaf nodes while respecting the partial order. Our study leads to conclude that, among these strategies, only Pure IDFS and a slight modification of improved LDS respect it.
Decomposition is it powerful technique for reducing the size of a backtracking search tree. However, when solving constraint optimization problems (COP'S) the standard technique of invoking a separate recursion to...
详细信息
ISBN:
(纸本)9783540859574
Decomposition is it powerful technique for reducing the size of a backtracking search tree. However, when solving constraint optimization problems (COP'S) the standard technique of invoking a separate recursion to solve each independent component can significantly reduce the strength of the bounds that can be applied when using branch rind bound techniques. In this paper we present a new search algorithm that can obtain many of the computational benefits of decomposition without having to resort to separate recursions. that is, the algorithm explores a standard OR tree not an AND-OR tree. In this way incremental information gathered from any component can be immediately applied to improve the bounding information for all of the other components. We also discuss how caching and local propagation can be combined with our approach and finally test our methods empirically to verify their potential.
Several types of symmetry have been identified and exploited in constraintprogramming, leading to large reductions in search time. We present a novel application of one such form of symmetry: detecting dynamic value ...
详细信息
ISBN:
(纸本)9783642406263;9783642406270
Several types of symmetry have been identified and exploited in constraintprogramming, leading to large reductions in search time. We present a novel application of one such form of symmetry: detecting dynamic value interchangeability in the random variables of a 2-stage stochastic problem. We use a real-world problem from the literature: finding an optimal investment plan to strengthen a transportation network, given that a future earthquake probabilistically destroys links in the network. Detecting interchangeabilities enables us to bundle together many equivalent scenarios, drastically reducing the size of the problem and allowing the exact solution of cases previously considered intractable and solved only approximately.
In this paper we show that the power of using k-consistency techniques in a constraint problem is precisely captured by using a particular inference rule, which we call positive-hyper-resolution, on the direct Boolean...
详细信息
ISBN:
(纸本)9783642153952
In this paper we show that the power of using k-consistency techniques in a constraint problem is precisely captured by using a particular inference rule, which we call positive-hyper-resolution, on the direct Boolean encoding of the CSP instance. We also show that current clause-learning SAT-solvers will deduce any positive-hyper-resolvent of a fixed size from a given set of clauses in polynomial expected time. We combine these two results to show that, without being explicitly designed to do so, current clause-learning SAT-solvers efficiently simulate k-consistency techniques, for all values of k. We then give some experimental results to show that this feature allows clause-learning SAT-solvers to efficiently solve certain families of CSP instances which are challenging for conventional CP solvers.
We introduce a propagator for abstract pairs of Sum constraints, where the expressions in the sums respect a form of convexity. this propagator is parametric and can be instantiated for various concrete pairs, includi...
详细信息
ISBN:
(纸本)9783642406263;9783642406270
We introduce a propagator for abstract pairs of Sum constraints, where the expressions in the sums respect a form of convexity. this propagator is parametric and can be instantiated for various concrete pairs, including Deviation, Spread, and the conjunction of Sum and Count. We show that despite its generality, our propagator is competitive in theory and practice with state-of-the-art propagators.
暂无评论