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).
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)
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.
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 constraint Optimization Problems (DCOPs) offer a powerful approach for the description and resolution of cooperative multi-agent problems. In this model, a group of agents coordinate their actions to optim...
详细信息
ISBN:
(纸本)9783319661582;9783319661575
Distributed constraint Optimization Problems (DCOPs) offer a powerful approach for the description and resolution of cooperative multi-agent problems. In this model, a group of agents coordinate their actions to optimize a global objective function, taking into account their preferences or constraints. A core limitation of this model is the assumption that the preferences of all agents or the costs of all constraints are specified a priori. Unfortunately, this assumption does not hold in a number of application domains where preferences or constraints must be elicited from the users. One of such domains is the Smart Home Device Scheduling (SHDS) problem. Motivated by this limitation, we make the following contributions in this paper: (1) We propose a general model for preference elicitation in DCOPs;(2) We propose several heuristics to elicit preferences in DCOPs;and (3) We empirically evaluate the effect of these heuristics on random binary DCOPs as well as SHDS problems.
Mobile robots in flexible manufacturing systems can transport components for jobs between machines as well as process jobs on selected machines. While the job shop problem with transportation resources allows encapsul...
详细信息
ISBN:
(纸本)9783030300487
Mobile robots in flexible manufacturing systems can transport components for jobs between machines as well as process jobs on selected machines. While the job shop problem with transportation resources allows encapsulating of transportation, this work concentrates on the extended version of the problem, including the processing by mobile robots. We propose a novel constraintprogramming model for this problem where the crucial part of the model lies in a proper inclusion of the transportation. We have implemented it in the Optimization programming Language using the CP Optimizer, and compare it withthe existing mixed integer programming solver. While both approaches are capable of solving the problem optimally, a new constraintprogramming approach works more efficiently, and it can compute solutions in more than an order of magnitude faster. Given that, the results of more realistic data instances are delivered in real-time, which is very important in a smart factory.
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.
this paper considers the automatic generation of architectural tests (ATGP), a fundamental problem in processor validation. ATGPs are complex conditional constraint satisfaction problems which typically feature both h...
详细信息
ISBN:
(纸本)9783642042430
this paper considers the automatic generation of architectural tests (ATGP), a fundamental problem in processor validation. ATGPs are complex conditional constraint satisfaction problems which typically feature both hard and soft constraints and very large domains (e.g., all memory addresses). Moreover, the goal is to generate a. large number of diverse Solutions under tight runtime constraints. To improve solution diversity, this paper proposes a, novel approach to ATGPs by modeling them as MAXDIVERSEkSET problems and solving them withconstraint-based local search over conditional variables. the paper presents the semantics and implementation of Conditional variables in this context and demonstrates the computational benefits of the approach.
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.
Efficient constraint propagation is crucial to any constraint solver. We show that watched literals, already a great success in the satisfiability community, can be used to provide highly efficient implementations of ...
详细信息
ISBN:
(纸本)3540462678
Efficient constraint propagation is crucial to any constraint solver. We show that watched literals, already a great success in the satisfiability community, can be used to provide highly efficient implementations of constraint propagators. We describe three important aspects of watched literals as we apply them to constraints, and how they are implemented in the MINION constraint solver. We show three successful applications of to constraint propagators: the sum of Boolean variables;GAC for the 'element' constraint;and GAC for the 'table' constraint.
暂无评论