this book constitutes the refereed proceedings of the 14thinternationalconference on principles and practice of constraintprogramming, cp 2008, Sydney, Australia, September, 2008. the 27 revised full papers and 23 ...
详细信息
ISBN:
(数字)9783540859581
ISBN:
(纸本)9783540859574
this book constitutes the refereed proceedings of the 14thinternationalconference on principles and practice of constraintprogramming, cp 2008, Sydney, Australia, September, 2008. the 27 revised full papers and 23 revised short papers presented together with 6 application papers and the abstracts of one invited lecture were carefully reviewed and selected from 120 submissions. All current issues of computing withconstraints are addressed, ranging from methodological and foundational aspects - using algorithms, environments, languages, models and systems - to solving real-world problems in various application fields.
the constraint satisfaction problem asks to decide if a set of constraints over a relational structure A is satisfiable (CSP(A)). We consider CSP(A ∪ B) where A is a structure and B is an alien structure, and analyse...
详细信息
Fuzzy constraints are it popular approach to handle preferences and over-constrained problems in scenarios where one needs to be cautious. Such as in medical or space applications. We consider here fuzzy constraint pr...
详细信息
ISBN:
(纸本)9783540859574
Fuzzy constraints are it popular approach to handle preferences and over-constrained problems in scenarios where one needs to be cautious. Such as in medical or space applications. We consider here fuzzy constraint problems where some of the preferences may be missing. this models, for example, settings where agents are distributed and have privacy issues, or where there is an ongoing preference elicitation process. In this setting. We Study how to find a solution which is optimal irrespective of the missing preferences. In the process of finding such it solution. we may elicit preferences from the user if necessary. However. our goal is to ask the user as little as possible. We define it combined solving and preference elicitation scheme with a large number of different instantiations, each corresponding to a concrete algorithm which we compare experimentally. We compute boththe number of elicited preferences and the "user effort", which may he larger, as it contains all the preference values the user has to compute to be able to respond to the elicitation requests. While the number of elicited preferences is important when the concern is to communicate its little information as possible, the user effort measures also the hidden work the user hits to do to be able to communicate the elicited preferences. Our experimental results show that Some of our algorithms are very good at finding a necessarily optimal Solution while asking the user for only a very small fraction of the missing preferences. the user effort is also very small for the best algorithms. Finally, we test these algorithms on hard constraint problems with possibly missing constraints, where the aim is to find feasible solutions irrespective of the missing constraints.
We introduce five constraint models for the 3-dimensional stable matching problem with cyclic preferences and study their relative performances under diverse configurations. While several constraint models have been p...
详细信息
the constraint satisfaction problem (CSP) is among the most studied computational problems. While NP-hard, many tractable subproblems have been identified (Bulatov 2017, Zuk 2017). Backdoors, introduced by Williams, G...
详细信息
Most CSP algorithms are based on refinements arid extensions of backtracking, and employ one of two simple "branching schemes": 2-way branching or d-way branching, for domain size d. the schemes are not equi...
详细信息
A constraint satisfaction problem instance consists of a collection of variables that need to have values assigned to them. the assignments are limited by constraints that force the values taken by certain collections...
详细信息
ISBN:
(纸本)3540202021
A constraint satisfaction problem instance consists of a collection of variables that need to have values assigned to them. the assignments are limited by constraints that force the values taken by certain collections of variables (the constraint scopes) to satisfy specified properties (the constraint relations). As the general CSP problem is NP-hard there has been significant effort devoted to discovering tractable subproblems of the CSP. the structure of a CSP instance is defined to be the hypergraph formed by the constraint scopes. Restricting the possible structure of the CSP instances has been a successful way of identifying tractable subproblems. the language of a CSP instance is defined to be the set of constraint relations of the instance. Restricting the language allowed for CSP instances has also yielded many interesting tractable subproblems. Almost all known tractable subproblems are either structural or relational. In this paper we construct tractable subproblems of the general CSP that are neither defined by structural nor relational properties. these new tractable classes are related to tractable languages in much the same way that general decompositions (cutset, tree-clustering, etc.) are related to acyclic decompositions. It may well be that our results will begin to make language based tractability of more practical interest. We show that our theory allows us to properly extend the binary maxclosed language based tractable class, which is maximal as a tractable binary constraint language. Our theory also explains the tractability of the constraint representation of the Stable Marriage Problem which has not been amenable to existing explanations of tractability. In fact we provide a uniform explanation for the tractability of the class of maxclosed CSPs and the SMP. there has been much work done on so called renamable HORN theories which are a tractable subproblem of SAT. It has been shown that renamable HORN theories are tractably identifiable and
暂无评论