the constraint satisfaction problem (CSP) can be formulated as the problem of deciding, given a pair (A, B) of relational structures, whether or not there is a homomorphism from A to B. Although the CSP is in general ...
详细信息
ISBN:
(纸本)3540232419
the constraint satisfaction problem (CSP) can be formulated as the problem of deciding, given a pair (A, B) of relational structures, whether or not there is a homomorphism from A to B. Although the CSP is in general intractable, it may be restricted by requiring the "target structure" B to be fixed;denote this restriction by CSP(B). In recent years, much effort has been directed towards classifying the complexity of all problems CSP(B). the acquisition of CSP(B) tractability results has generally proceeded by isolating a class of relational structures B believed to be tractable, and then demonstrating a polynomial-time algorithm for the class. In this paper, we introduce a new approach to obtaining CSP(B) tractability results: instead of starting with a class of structures, we start with an algorithm called look-ahead arc consistency, and give an algebraic characterization of the structures solvable by our algorithm. this characterization is used both to identify new tractable structures and to give new proofs of known tractable structures.
constraintprogramming is becoming competitive for solving certain data-mining problems largely due to the development of global constraints. We introduce the CoverSize constraint for itemset mining problems, a global...
详细信息
ISBN:
(纸本)9783319661582;9783319661575
constraintprogramming is becoming competitive for solving certain data-mining problems largely due to the development of global constraints. We introduce the CoverSize constraint for itemset mining problems, a global constraint for counting and constraining the number of transactions covered by the itemset decision variables. We show the relation of this constraint to the well-known table constraint, and our filtering algorithm internally uses the reversible sparse bitset data structure recently proposed for filtering table. Furthermore, we expose the size of the cover as a variable, which opens up new modelling perspectives compared to an existing global constraint for (closed) frequent itemset mining. For example, one can constrain minimum frequency or compare the frequency of an itemset in different datasets as is done in discriminative itemset mining. We demonstrate experimentally on the frequent, closed and discriminative itemset mining problems that the CoverSize constraint with reversible sparse bitsets allows to outperform other CP approaches.
this paper introduces a generalization of the nvalue constraintthat bounds the number of distinct values taken by a set of variables. the generalized constraint (called nvector) bounds the number of distinct;vectors....
详细信息
ISBN:
(纸本)9783642042430
this paper introduces a generalization of the nvalue constraintthat bounds the number of distinct values taken by a set of variables. the generalized constraint (called nvector) bounds the number of distinct;vectors. the first contribution of this paper is to show that this global constraint has a significant role to play with continuous domains, by taking the example of simultaneous localization and map building (SLAM). this type of problem arises in the context, of mobile robotics. the second contribution is, to prove that enforcing bound consistency on this constraint is NP-complete. A simple contractor (or propagator) is proposed and applied on a real application.
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.
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 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.
暂无评论