Dynamic constraint Satisfaction Problems play a very important role in modeling and solving real-life problems where the set of constraints is changing. the paper addresses a problem of maintaining arc consistency aft...
详细信息
ISBN:
(纸本)3540232419
Dynamic constraint Satisfaction Problems play a very important role in modeling and solving real-life problems where the set of constraints is changing. the paper addresses a problem of maintaining arc consistency after removing a constraint from the constraint model. A new dynamic arc consistency algorithm is proposed that improves the practical time efficiency of the existing AC\DC algorithm by using additional data-structures. the algorithm achieves real time efficiency close to the so far fastest DynAC-6 algorithm while keeping the memory consumption low.
We propose a new method for solving Valued constraint Satisfaction Problems based both on backtracking techniques-branch and bound- and the notion of tree-decomposition of valued constraint networks. this mixed method...
详细信息
ISBN:
(纸本)3540202021
We propose a new method for solving Valued constraint Satisfaction Problems based both on backtracking techniques-branch and bound- and the notion of tree-decomposition of valued constraint networks. this mixed method aims to benefit from the practical efficiency of enumerative algorithms while providing a warranty of a bounded time complexity. Indeed the time complexity of our method is O(d(w+)+ (1)) with w(+) an approximation of the tree-width of the constraint network and d the maximum size of domains. Such a complexity is obtained by exploiting optimal bounds on the sub-problems defined from the tree-decomposition. these bounds associated to some partial assignments are called "structural valued goods". Recording and exploiting these goods may allow our method to save some time and space with respect to ones required by classical dynamic programming methods. Finally, this method is a natural extension of the BTD algorithm [1] proposed in the classical CSP framework.
constraint satisfaction has been applied with great success in closed-world scenarios, where all options and constraints are known from the beginning and fixed. Withthe internet, many of the traditional CSP applicati...
详细信息
ISBN:
(纸本)3540202021
constraint satisfaction has been applied with great success in closed-world scenarios, where all options and constraints are known from the beginning and fixed. Withthe internet, many of the traditional CSP applications in resource allocation, scheduling and planning pose themselves in open-world settings, where options and constraints must be gathered from different agents in a network. We define open constraint optimization as a model of such tasks. Under the assumption that options are discovered in decreasing order of preference, it becomes possible to guarantee optimality even when domains and constraints are not completely known. We propose several algorithms for solving open constraint optimization problems by incrementally gathering options through the network. We report empirical results on their performance on random problems, and analyze how to achieve optimality with a minimal number of queries to the information sources.
Symmetry in constraint problems can be exploited to greatly improve search performance. A form of symmetry that has been the subject of considerable research is value interchangeability. Automatically detecting full i...
详细信息
ISBN:
(纸本)3540232419
Symmetry in constraint problems can be exploited to greatly improve search performance. A form of symmetry that has been the subject of considerable research is value interchangeability. Automatically detecting full interchangeability is thought to be intractable, so research has focused on either discovery of local interchangeability or programmer knowledge of full interchangeability. this paper shows that full dynamic substitutability can be broken in a CSP by reformulating it as a SAT problem. No analysis is necessary, space requirements are modest, solutions are collected into Cartesian products, and unit propagation enforces forward checking on the CSP. In experiments on unsatisfiable problems, better results are obtained than with standard SAT encodings.
We study from a formal perspective the consistency and propagation of constraints involving multiset variables. that is, variables whose values are multisets. these help us model problems more naturally and can, for e...
详细信息
ISBN:
(纸本)3540202021
We study from a formal perspective the consistency and propagation of constraints involving multiset variables. that is, variables whose values are multisets. these help us model problems more naturally and can, for example, prevent introducing unnecessary symmetry into a model. We identify a number of different representations for multiset variables and compare them. We then propose a definition of local consistency for constraints involving multiset, set and integer variables. this definition is a generalization of the notion of bounds consistency for integer variables. We show how this local consistency property can be enforced by means of some simple inference rules which tighten bounds on the variables. We also study a number of global constraints on set and multiset variables. Surprisingly, unlike finite domain variables, the decomposition of global constraints over set or multiset variables often does not hinder constraint propagation.
Existing random models for the constraint satisfaction problem (CSP) all require an extremely low constraint tightness in order to have non-trivial threshold behaviors and guaranteed hard instances at the threshold. W...
详细信息
ISBN:
(纸本)3540232419
Existing random models for the constraint satisfaction problem (CSP) all require an extremely low constraint tightness in order to have non-trivial threshold behaviors and guaranteed hard instances at the threshold. We study the possibility of designing random CSP models that have interesting threshold and typical-case complexity behaviors while at the same time, allow a much higher constraint tightness. We show that random CSP models that enforce the constraint consistency have guaranteed exponential resolution complexity without putting much restriction on the constraint tightness. A new random CSP model is proposed to generate random CSPs with a high tightness whose instances are always consistent. Initial experimental results are also reported to illustrate the sensitivity of instance hardness to the constraint tightness in classical CSP models and to evaluate the proposed new random CSP model.
Answer Set programming (ASP; [1,2,3]) is a declarative problem solving approach, combining a rich yet simple modeling language with high-performance Boolean constraint solving capacities. ASP is particularly suited fo...
详细信息
ISBN:
(纸本)9783642406263;9783642406270
Answer Set programming (ASP; [1,2,3]) is a declarative problem solving approach, combining a rich yet simple modeling language with high-performance Boolean constraint solving capacities. ASP is particularly suited for modeling problems in the area of Knowledge Representation and Reasoning involving incomplete, inconsistent, and changing information. As such, it offers, in addition to satisfiability testing, various reasoning modes, including different forms of model enumeration, intersection or unioning, as well as multi-criteria and -objective optimization. From a formal perspective, ASP allows for solving all search problems in NP (and NP NP ) in a uniform way. Hence, ASP is wellsuited for solving hard combinatorial search problems, like system design and timetabling. Prestigious applications of ASP include composition of Renaissance music [4], decision support systems for NASA shuttle controllers [5], reasoning tools in systems biology [6,7,8] and robotics [9,10], industrial team-building [11], and many more. the versatility of ASP is nicely reflected by the ASP solver clasp [12], winning first places at various solver competitions, such as ASP,MISC, PB, and SAT competitions. the solver clasp is at the heart of the open source platform Potassco hosted at *** . Potassco stands for the “Potsdam Answer Set Solving Collection-[13] and has seen more than 30000 downloads world-wide since its inception at the end of 2008. the talk will start with an introduction to ASP, its modeling language and solving methodology, and portray some distinguished ASP systems.
暂无评论