Since the early 90's that constraint Logic programming (CLP) has been used to solve Combinatorial Search Problems. Generally, CLP has a good performance with highly constrained problems, but it lacks a "globa...
详细信息
ISBN:
(纸本)3540202021
Since the early 90's that constraint Logic programming (CLP) has been used to solve Combinatorial Search Problems. Generally, CLP has a good performance with highly constrained problems, but it lacks a "global perspective" of the search space, making the search for the optimal solution more difficult when the problems becomes larger and less constrained. On the other hand, Local Search Methods explore the search space directly through an "intelligent" construction of solution neighbourhoods, turning these methods suitable for solving less constrained and large search spaces problems. the aim of this paper is to present a hybridisation framework that allows combining Local Search methods withconstraint Logic programming. the first results demonstrate that while maintaining the CLP strengths it is possible to overcome their weaknesses and improve its search efficiency.
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...
详细信息
One of the most appealing features of constraintprogramming is its rich constraint language for expressing combinatorial optimization problems. this paper demonstrates that traditional combinators from constraint pro...
详细信息
ISBN:
(纸本)3540232419
One of the most appealing features of constraintprogramming is its rich constraint language for expressing combinatorial optimization problems. this paper demonstrates that traditional combinators from constraintprogramming have natural counterparts for local search, although their underlying computational model is radically different. In particular, the paper shows that constraint combinators, such as logical and cardinality operators, reification, and first-class expressions can all be viewed as differentiable objects. these combinators naturally support elegant and efficient modelings, generic search procedures, and partial constraint satisfaction techniques for local search. Experimental results on a variety of applications demonstrate the expressiveness and the practicability of the combinators.
the contribution of this paper is in demonstrating the impact of AND/OR search spaces view on solutions counting. In contrast to the traditional (OR) search space view, the AND/OR search space displays independencies ...
详细信息
ISBN:
(纸本)3540232419
the contribution of this paper is in demonstrating the impact of AND/OR search spaces view on solutions counting. In contrast to the traditional (OR) search space view, the AND/OR search space displays independencies present in the graphical model explicitly and may sometimes reduce the search space exponentially. Empirical evaluation focusing on counting demonstrates the spectrum of search and inference within the AND/OR search spaces.
A wide range of counting and occurrence constraints can be specified with just two global primitives: the RANGE constraint, which computes the range of values used by a sequence of variables, and the ROOTS constraint,...
详细信息
ISBN:
(纸本)3540462678
A wide range of counting and occurrence constraints can be specified with just two global primitives: the RANGE constraint, which computes the range of values used by a sequence of variables, and the ROOTS constraint, which computes the variables mapping onto a set of values. We focus here on the ROOTS constraint. We show that propagating the ROOTS constraint completely is intractable. We therefore propose a decomposition which can be used to propagate the constraint in linear time. Interestingly, for all uses of the ROOTS constraint we have met, this decomposition does not destroy the global nature of the constraint as we still prune all possible values. In addition, even when the ROOTS constraint is intractable to propagate completely, we can enforce bound consistency in linear time simply by enforcing bound consistency on the decomposition. Finally, we show that specifying counting and occurrence constraints using ROOTS is effective and efficient in practice on two benchmark problems from CSPLib.
the quantified constraint satisfaction problem (QCSP) is a natural and useful generalization of the constraint satisfaction problem (CSP) in which both universal and existential quantification of variables is permitte...
详细信息
ISBN:
(纸本)3540232419
the quantified constraint satisfaction problem (QCSP) is a natural and useful generalization of the constraint satisfaction problem (CSP) in which both universal and existential quantification of variables is permitted. Because the CSP and QCSP are in general intractable, much effort has been directed towards identifying restricted cases of these problems that are tractable in polynomial time. In this paper, we investigate restricted cases of the QCSP having 2-semilattice polymorphisms. We prove a complete classification of 2-semilattice polymorphisms, demonstrating that each gives rise to a case of the QCSP that is either tractable in polynomial time, or coNP-hard.
We show an algorithm for bound consistency of global cardinality constraints, which runs in time O(n+n') plus the time required to sort the assignment variables by range endpoints, where n is the number of assignm...
详细信息
ISBN:
(纸本)3540202021
We show an algorithm for bound consistency of global cardinality constraints, which runs in time O(n+n') plus the time required to sort the assignment variables by range endpoints, where n is the number of assignment variables and n' is the number of values in the union of their ranges. We thus offer a fast alternative to Regin's arc consistency algorithm [6] which runs in time O(n(3/2) n') and space O(n . n'). Our algorithm can also narrow the bounds for the number of occurrences of each value, which has not been done before.
GSAT has been proven highly effective for solving certain classes of large SAT problems. It starts from a randomly generated truth assignment and tries to reduce the number of violated clauses by iteratively flipping ...
详细信息
暂无评论