constraintprogramming is rapidly becoming the technology of choice for modelling and solving complex combinatorial problems. However, users of this technology need significant expertise in order to model their proble...
详细信息
ISBN:
(纸本)3540292438
constraintprogramming is rapidly becoming the technology of choice for modelling and solving complex combinatorial problems. However, users of this technology need significant expertise in order to model their problems appropriately. the lack of availability of such expertise is a significant bottleneck to the broader uptake of constraint technology in the real world. We present a new SAT-based version space algorithm for acquiring constraint satisfaction problems from examples of solutions and non-solutions of a target problem. An important advantage is the ease with which domain-specific knowledge can be exploited using the new algorithm. Finally, we empirically demonstrate the algorithm and the effect of exploiting domain-specific knowledge on improving the quality of the acquired constraint network.
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.
At the first PPCP conference in 1995, I was honored to be one of the invited speakers. Twenty conferences later, much has changed in the computational *** have seen the penetration of the Internet in every aspect of h...
ISBN:
(纸本)9783319104287;9783319104270
At the first PPCP conference in 1995, I was honored to be one of the invited speakers. Twenty conferences later, much has changed in the computational *** have seen the penetration of the Internet in every aspect of human life; the establishment of the multi-core era; the arrival of petaflop high performance computing; the rise of big data, analytics and machine learning; and the emergence of the planet-wide computer (the “cloud-.
System dynamics is often modeled by means of parametric differential equations. Despite their expressive power, they are difficult to reason about and make safe decisions, given their non-linearity and the important e...
详细信息
ISBN:
(纸本)3540202021
System dynamics is often modeled by means of parametric differential equations. Despite their expressive power, they are difficult to reason about and make safe decisions, given their non-linearity and the important effects that the uncertainty on data may cause. Either by traditional numerical simulation or relying on constraint based methods, it is difficult to express a number of constraints on the solution functions (for which there are usually no analytical solutions) and these constraints may only be handled passively, with generate and test techniques. In contrast, the framework we propose not only extends the declarativeness of the constraint based approach but also makes an active use of constraints on the solution functions, which makes it particularly suited for a number of decision making problems, such as those arising in the biomedical applications presented in the paper.
constraints have played a central role in cp because they capture key substructures of a problem and efficiently exploit them to boost inference. this paper intends to do the same thing for search, proposing constrain...
详细信息
constraints have played a central role in cp because they capture key substructures of a problem and efficiently exploit them to boost inference. this paper intends to do the same thing for search, proposing constraint-centered heuristics which guide the exploration of the search space toward areas that are likely to contain a high number of solutions. We first propose new search heuristics based on solution counting information at the level of individual constraints. We then describe efficient algorithms to evaluate the number of solutions of two important families of constraints: occurrence counting constraints, such as all different, and sequencing constraints, such as regular. In both cases we take advantage of existing filtering algorithms to speed up the evaluation. Experimental results on benchmark problems show the effectiveness of our approach.
We show that intractability of the constraint satisfaction problem over a fixed finite constraint language can, in all known cases, be replaced by an infinite hierarchy of intractable promise problems of increasingly ...
详细信息
ISBN:
(纸本)9783319661582;9783319661575
We show that intractability of the constraint satisfaction problem over a fixed finite constraint language can, in all known cases, be replaced by an infinite hierarchy of intractable promise problems of increasingly disparate promise conditions. the instances are guaranteed to either have no solutions at all, or to be k-robustly satisfiable (for any fixed k), meaning that every "reasonable" partial instantiation on k variables extends to a solution.
暂无评论