the connection between constraint languages and clone theory has been a fruitful line of research on the complexity of constraint satisfaction problems. In a recent result, Cohen et al. [SIAM J. Comput., 42 (2013), pp...
详细信息
the connection between constraint languages and clone theory has been a fruitful line of research on the complexity of constraint satisfaction problems. In a recent result, Cohen et al. [SIAM J. Comput., 42 (2013), pp. 915-1939] have characterized a Galois connection between valued constraint languages and so-called weighted clones. In this paper, we study the structure of weighted clones. We extend the results of Creed and. Zivny from [Proceedings of the 17thinternationalconference on principles and practice of constraintprogramming, 2011, pp. 210-224] on types of weightings necessarily contained in every nontrivial weighted clone. this result has immediate computational complexity consequences as it provides necessary conditions for tractability of weighted clones and thus valued constraint languages. We demonstrate that some of the necessary conditions are also sufficient for tractability, while others are provably not.
Counting the number of solutions to CSP instances has vast applications in several areas ranging from statistical physics to artificial intelligence. We provide a new algorithm for counting the number of solutions to ...
详细信息
ISBN:
(纸本)3540202021
Counting the number of solutions to CSP instances has vast applications in several areas ranging from statistical physics to artificial intelligence. We provide a new algorithm for counting the number of solutions to binary CSP s which has a time complexity ranging from O ((d/4 . alpha(4))(n)) to O((alpha + alpha(5) + [d/4 - 1] . alpha(4))(n)) (where alpha approximate to 1.2561) depending on the domain size d greater than or equal to 3. this is substantially faster than previous algorithms, especially for small d. We also provide an algorithm for counting k-colourings in graphs and its running time ranges from O ([log(2) k](n)) to O ([log(2) k + 1](n)) depending on k greater than or equal to 4. Previously, only an O(1.8171(n)) time algorithm for counting 3-colourings were known, and we improve this upper bound to O(1.7879(n)).
It has long been accepted that dynamic variable ordering heuristics outperform static orderings. But just how dynamic are dynamic variable ordering heuristics? this paper examines the behaviour of a number of heuristi...
详细信息
ISBN:
(纸本)3540652248
It has long been accepted that dynamic variable ordering heuristics outperform static orderings. But just how dynamic are dynamic variable ordering heuristics? this paper examines the behaviour of a number of heuristics: and attempts to measure the entropy of the search process at different depths in the search tree.
the use of constraint optimization has recently proven to be a successful approach to providing solutions to various NP-hard search and optimization problems in data analysis. In this work we extend the use of constra...
详细信息
ISBN:
(纸本)9783319661582;9783319661575
the use of constraint optimization has recently proven to be a successful approach to providing solutions to various NP-hard search and optimization problems in data analysis. In this work we extend the use of constraint optimization systems further within data analysis to a central problem arising from the analysis of multivariate data, namely, determining minimum-width multivariate confidence intervals, i.e., the minimum-width confidence band problem (MWCB). Pointing out drawbacks in recently proposed formalizations of variants of MWCB, we propose a new problem formalization which generalizes the earlier formulations and allows for circumvention of their drawbacks. We present two constraint models for the new problem in terms of mixed integer programming and maximum satisfiability, as well as a greedy approach. Furthermore, we empirically evaluate the scalability of the constraint optimization approaches and solution quality compared to the greedy approach on real-world datasets.
A typical technique in integer programming for filtering variables is known as variable fixing. the optimal dual solution of the linear relaxation can be used to detect some of the 0/1 variables that must be fixed to ...
详细信息
ISBN:
(纸本)9783319661582;9783319661575
A typical technique in integer programming for filtering variables is known as variable fixing. the optimal dual solution of the linear relaxation can be used to detect some of the 0/1 variables that must be fixed to either 0 or 1 in any solution improving the best known, but this filtering is incomplete. A complete technique is proposed in this paper for satisfaction problems with an ideal integer programming formulation. We show, in this case, that the 0/1 variables taking the same value in all solutions can be identified by solving a single linear program with twice the number of the original variables. In other words, a complete variable fixing of the 0/1 variables can be performed for a small overhead. As a result, this technique can be used to design generic arc consistency algorithms. We believe it is particularly useful to quickly prototype arc consistency algorithms for numerous polynomial constraints and demonstrate it for the family of Sequence global constraints.
Several constraint satisfaction algorithms focus on numeric constraint satisfaction problems (CSPs). A numeric CSP is defined by a set of variables, their domains, intervals in ?\Re, and the set of constraints, expres...
ISBN:
(纸本)3540666265
Several constraint satisfaction algorithms focus on numeric constraint satisfaction problems (CSPs). A numeric CSP is defined by a set of variables, their domains, intervals in ?\Re, and the set of constraints, expressed as mathematical relations, which must be satisfied for any solution. Such CSPs can model many engineering and design problems from domains such as mechanical, electrical and civil engineering.
We introduce a definition of constraint symmetry for soft CSPs, based on the definition of constraint symmetry for classical CSPs. We show that the constraint symmetry group of a soft CSP is a subgroup of that of an a...
详细信息
ISBN:
(纸本)9783540749691
We introduce a definition of constraint symmetry for soft CSPs, based on the definition of constraint symmetry for classical CSPs. We show that the constraint symmetry group of a soft CSP is a subgroup of that of an associated classical CSP instance. Where it is smaller, we can successfully exploit the additional symmetries using conditional symmetry breaking. We demonstrate, in a case-study of graph colouring, that eliminating the symmetry of the soft CSP combined with conditional symmetry breaking can lead to huge reductions in the search effort to find an optimal solution to the soft CSP.
We describe some new propagators for breaking symmetries in constraint satisfaction problems. We also introduce symmetry breaking constraints to deal with symmetries acting simultaneously on variables and values, cond...
详细信息
ISBN:
(纸本)3540462678
We describe some new propagators for breaking symmetries in constraint satisfaction problems. We also introduce symmetry breaking constraints to deal with symmetries acting simultaneously on variables and values, conditional symmetries, as well as symmeties acting on set and other types of variables.
In this paper, we describe a new algorithm for sampling solutions from a uniform distribution over the solutions of a constraint network. Our new algorithm improves upon the Sampling/Importance Resampling (SIR) compon...
详细信息
ISBN:
(纸本)9783540859574
In this paper, we describe a new algorithm for sampling solutions from a uniform distribution over the solutions of a constraint network. Our new algorithm improves upon the Sampling/Importance Resampling (SIR) component of our previous scheme of SampleSearch-SIR by taking advantage of the decomposition implied by the network's AND/OR search space. We also describe how our new scheme can approximately count and lower bound the number of solutions of a constraint network. We demonstrate boththeoretically and empirically that our new algorithm yields far better performance than competing approaches.
In constraint Satisfaction, basic inferences rely oil some properties of constraint networks, called consistencies, that allow the identification of inconsistent instantiations (also called nogoods). Two main families...
详细信息
ISBN:
(纸本)9783642042430
In constraint Satisfaction, basic inferences rely oil some properties of constraint networks, called consistencies, that allow the identification of inconsistent instantiations (also called nogoods). Two main families of consistencies have been introduced so far: those that permit LIS to reason from variables Such as (i, j)-consistency and those that permit us to reason from constraints Such as relational (i, j)-consistency. this paper introduces a new family of consistencies based on the concept of flailed value (a value pruned during search). this family is orthogonal to previous ones.
暂无评论