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.
Several branching heuristics for compiling in a top-down fashion finite-domain constraint networks into multi-valued decision diagrams (MDD) or decomposable multi-valued decision graphs (MDDG) are empirically evaluate...
详细信息
ISBN:
(纸本)9783319661582;9783319661575
Several branching heuristics for compiling in a top-down fashion finite-domain constraint networks into multi-valued decision diagrams (MDD) or decomposable multi-valued decision graphs (MDDG) are empirically evaluated, using the cn2mddg compiler. this MDDG compiler has been enriched with various additional branching rules. these rules can be gathered into two families, the one consisting of heuristics for the satisfaction problem (which are suited to compiling networks into MDD representations) and the family of heuristics favoring decompositions (which are relevant when the MDDG language is targeted). Our empirical investigation on a large dataset shows the value of decomposability (targeting MDDG allows for compiling many more instances and leads to much smaller compiled representations). the well-known (Dom/Wdeg) heuristics appears as the best choice for compiling networks into MDD. When MDDG is the target, a new rule, based on a dynamic, yet parsimonious use of hypergraph partitioning for the decomposition purpose turns out to be the best option. As expected, the best heuristics for the satisfaction problem perform better than the best heuristics favoring decompositions when MDD is targeted, and the converse is the case when MDDG is targeted.
Forbidden patterns problems are a generalisation of (finite) constraint satisfaction problems which are definable in Feder and Vardi9;s logic MMSNP [1]. in fact, they are examples of infinite constraint satisfactio...
详细信息
ISBN:
(纸本)9783642153952
Forbidden patterns problems are a generalisation of (finite) constraint satisfaction problems which are definable in Feder and Vardi's logic MMSNP [1]. in fact, they are examples of infinite constraint satisfaction problems with nice model theoretic properties introduced by Bodirsky [2]. In previous work [3], we introduced a normal form for these forbidden patterns problems which allowed us to provide an effective characterisation of when a problem is a finite or infinite constraint satisfaction problem. One of the central concepts of this normal form is that of a recolouring. In the presence of a recolouring from a forbidden patterns problem Omega(1) to another forbidden patterns problem Omega(2), containment of Omega(1) in Omega(2) follows. the converse does not hold in general and it remained open whether it did in the case of problems being given in our normal form. In this paper, we prove that this is indeed the case. We also show that the recolouring problem is Pi(p)(2)-harpd and in Sigma(p)(3).
In this paper, the embodiment design of an air conditioning system (ACS) in an aircraft is investigated using interval constraint satisfaction techniques. the detailed ACS model is quite complex to solve, since it con...
详细信息
ISBN:
(纸本)9783540749691
In this paper, the embodiment design of an air conditioning system (ACS) in an aircraft is investigated using interval constraint satisfaction techniques. the detailed ACS model is quite complex to solve, since it contains many coupled variables and many constraints corresponding to complex physics phenomena. Some new heuristics and notions based on embodiment design knowledge, are briefly introduced to undertake some embodiment design concepts and to obtain a more relevant and more efficient solving process than classical algorithms. the benefits of using constraintprogramming in embodiment design are discussed and some difficulties for designers using CP tools are shortly detailed.
Equidistant Frequency Permutation Arrays are combinatorial objects of interest in coding theory. A frequency permutation array is a type of constant composition code in which each symbol Occurs the same number of time...
详细信息
ISBN:
(纸本)9783642042430
Equidistant Frequency Permutation Arrays are combinatorial objects of interest in coding theory. A frequency permutation array is a type of constant composition code in which each symbol Occurs the same number of times in each codeword. the problem is to find a set of codewords Such that any pair of codewords are a given uniform Hamming distance apart. the equidistant case is of special interest given the result that any optimal constant composition code is equidistant. this paper presents, compares and combines a number of different constraint formulations of this problem class, including a new method of representing permutations withconstraints. Using these constraint models, we are able to establish several new results, which are contributing directly to mathematical research in this area.(1)
We consider soft constraint problems where some of the preferences may be unspecified. this models, for example, situations with several agents providing the data, or with possible privacy issues. In this context, we ...
详细信息
ISBN:
(纸本)9783540749691
We consider soft constraint problems where some of the preferences may be unspecified. this models, for example, situations with several agents providing the data, or with possible privacy issues. In this context, we study how to find an optimal solution without having to wait for all the preferences. In particular, we define an algorithm to find a solution which is necessarily optimal, that is, optimal no matter what the missing data will be, withthe aim to ask the user to reveal as few preferences as possible. Experimental results show that in many cases a necessarily optimal solution can be found without eliciting too many preferences.
In this paper we present and evaluate an evolutionary approach for learning new constraint satisfaction algorithms, specifically for MAX-SAT optimisation problems. Our approach offers two significant advantages over e...
详细信息
ISBN:
(纸本)3540292381
In this paper we present and evaluate an evolutionary approach for learning new constraint satisfaction algorithms, specifically for MAX-SAT optimisation problems. Our approach offers two significant advantages over existing methods: it allows the evolution of more complex combinations of heuristics, and;it can identify fruitful synergies among heuristics. Using four different classes of MAX-SAT problems, we experimentally demonstrate that algorithms evolved withthis method exhibit superior performance in comparison to general purpose methods.
the SEQUENCE constraint is useful in modelling car sequencing, rostering, scheduling and related problems. We introduce half a dozen new encodings of the SEQUENCE constraint, some of which do not hinder propagation. W...
详细信息
ISBN:
(纸本)9783540749691
the SEQUENCE constraint is useful in modelling car sequencing, rostering, scheduling and related problems. We introduce half a dozen new encodings of the SEQUENCE constraint, some of which do not hinder propagation. We prove that, down a branch of a search tree, domain consistency can be enforced on the SEQUENCE constraint in just O(n(2) log n) time. this improves upon the previous bound of O(n(3)) for each call down the tree. We also consider a generalization of the SEQUENCE constraint - the Multiple SEQUENCE constraint. Our experiments suggest that, on very large and tight problems, domain consistency algorithms are best. However, on smaller or looser problems, much simpler encodings are better, even though these encodings hinder propagation. When there are multiple SEQUENCE constraints, a more expensive propagator shows promise.
tIn this paper we give an overview of applications of constraintprogramming for IP (Internet Protocol) data networks, and discuss the problem of Resilience Analysis in more detail. In this problem we try to predict t...
详细信息
ISBN:
(纸本)3540462678
tIn this paper we give an overview of applications of constraintprogramming for IP (Internet Protocol) data networks, and discuss the problem of Resilience Analysis in more detail. In this problem we try to predict the loading of a network in different failure scenarios, without knowing end-to-end flow values throughout the network;the inference is based only on observed link traffic values. the related problem of Traffic Flow Analysis aims to derive a traffic matrix from the observed link traffic data. this is a severely under-constrained problem, we can show that the obtained flow values vary widely in different, feasible solutions. Experimental results indicate that using the same data much more accurate, bounded results can be obtained for Resilience Analysis.
the problem of finding an optimal solution in a constraint satisfaction problem with preferences has attracted a lot of researchers in Artificial Intelligence in general, and in the constraintprogramming community in...
详细信息
ISBN:
(纸本)9783540859574
the problem of finding an optimal solution in a constraint satisfaction problem with preferences has attracted a lot of researchers in Artificial Intelligence in general, and in the constraintprogramming community in particular. As a consequence, several approaches for expressing and reasoning about satisfiability problems with preferences have been proposed, and viable solutions exist for finding one optimal Solution. However, in many cases, it is not desirable to find just one solution. Indeed, it might be desirable to he able to compute more, and possibly all, optimal solutions, e.g.. for comparatively evaluate them on the basis of other criteria not captured by the preferences. In this paper we present a procedure for computing all optimal solutions of a satisfiability problem with preferences. the procedure is guaranteed to compute all and only the optimal solutions, i.e., models which are not optimal are not even computed.
暂无评论