检索结果-内蒙古大学图书馆

Balancing Asymmetry in Max-sum Using Split constraint Factor Graphs 1

24th international conference on the principles and practice of constraint programming (cp)

作者： Cohen, Liel Zivan, Roie Ben Gurion Univ Negev Beer Sheva Israel

ISBN: (数字)9783319983349

ISBN: (纸本)9783319983349;9783319983332

Max-sum is a version of Belief Propagation, used for solving DCOPs. On tree-structured problems, Max-sum converges to the optimal solution in linear time. When the constraint graph representing the problem includes multiple cycles, Max-sum might not converge and explore low quality solutions. Damping is a method that increases the chances that Max-sum will converge. Damped Max-sum (DMS) was recently found to produce high quality solutions for DCOP when combined with an anytime framework. We propose a novel method for adjusting the level of asymmetry in the factor graph, in order to achieve a balance between exploitation and exploration, when using Max-sum for solving DCOPs. By converting a standard factor graph to an equivalent split constraint factor graph (SCFG), in which each function-node is split to two function-nodes, we can control the level of asymmetry for each constraint. Our empirical results demonstrate that by applying DMS to SCFGs with a minor level of asymmetry we can find high quality solutions in a small number of iterations, even without using an anytime framework. As part of our investigation of this success, we prove that for a factor-graph with a single constraint, if this constraint is split symmetrically, Max-sum applied to the resulting cycle is guaranteed to converge to the optimal solution and demonstrate that for an asymmetric split, convergence is not guaranteed.

关键词： Belief propagation

来源：评论

学校读者我要写书评

暂无评论

constraints for breaking more row and column symmetries

引用

9th international conference on principles and practice of constraint programming, cp 2003

作者： Frisch, Alan M. Jefferson, Chris Miguel, Ian Artificial Intelligence Group Department of Computer Science University of York York United Kingdom

ISBN: (纸本)3540202021

constraint programs containing a matrix of two (or more) dimensions of decision variables often have row and column symmetries: in any assignment to the variables the rows can be swapped and the columns can be swapped without affecting whether or not the assignment is a solution. this introduces an enormous amount of redundancy when searching a space of partial assignments. It has been shown previously that one can remove consistently some of these symmetries by extending such a program with constraints that require the rows and columns to be lexicographically ordered. this paper identifies and studies the properties of a new additional constraint—the first row is less than or equal to all permutations of all other rows—that can be added consistently to break even more symmetries. Two alternative implementations of this stronger symmetry-breaking method are investigated, one of which employs a new algorithm that in time linear in the size of the matrix enforces the constraint that the first row is less than or equal to all permutations of all other rows. It is demonstrated experimentally that our method for breaking more symmetries substantially reduces search effort. © Springer-Verlag Berlin Heidelberg 2003.

关键词： constraint theory

来源：评论

学校读者我要写书评

暂无评论

Decomposition of the NVALUE constraint

Decomposition of the NVALUE Constraint

引用

16th Annual international conference on the principles and practice of constraint programming

作者： Bessiere, Christian Katsirelos, George Narodytska, Nina Quimper, Claude-Guy Walsh, Toby CNRS LIRMM Montpellier France CNRS CRIL Lens France NICTA Sydney NSW Australia Univ NSW Sydney NSW Australia Univ Laval Quebec City PQ G1K 7P4 Canada

ISBN: (纸本)9783642153952

We study decompositions of the global NVALUE constraint. Our main contribution is theoretical: we show that there are propagators for global constraints like NVALUE which decomposition can simulate with the same time complexity but with a much greater space complexity. this suggests that the benefit of a global propagator may often not be in saving time but in saving space. Our other theoretical contribution is to show for the first time that range consistency can be enforced on NVALUE with the same worst-case time complexity as bound consistency. Finally, the decompositions we study are readily encoded as linear inequalities. We are therefore able to use them in integer linear programs.

关键词： Integer programming

来源：评论

学校读者我要写书评

暂无评论

Improving backtrack search for solving the TCSP

引用

9th international conference on principles and practice of constraint programming, cp 2003

作者： Xu, Lin Choueiry, Berthe Y. Constraint Systems Laboratory Department of Computer Science and Engineering University of Nebraska-Lincoln LincolnNE United States

ISBN: (纸本)3540202021

In this paper, we address the task of finding the minimal network of a Temporal constraint Satisfaction Problem (TCSP).We report the integration of three approaches to improve the performance of the exponential-time backtrack search (BT-TCSP) proposed by Dechter et al. [6] for this purpose. the first approach consists of using a new efficient algorithm (∆STP) [21] for solving the Simple Temporal Problem (STP), an operation that must be executed at each node expansion during BT-TCSP. the second approach improves BT-TCSP itself by exploiting the topology of the temporal network. this is accomplished in three ways: finding and exploiting articulation points (AP), checking the graph for new cycles (NewCyc), and using a newheuristic for edge ordering (EdgeOrd). the third approach is a filtering algorithm, ∆AC, which is used as a preprocessing step to BT-TCSP, and which significantly reduces the size of the TCSP [22]. In addition to introducing two new techniques, NewCyc and EdgeOrd, this paper discusses an extensive evaluation of the merits of the above three approaches. Our experiments on randomly generated problems demonstrate significant improvements in the number of nodes visited, constraint checks, and cpU time. © Springer-Verlag Berlin Heidelberg 2003.

关键词： constraint satisfaction problems

来源：评论

学校读者我要写书评

暂无评论

Symmetry definitions for constraint satisfaction problems

引用

constraintS 2006年第2-3期11卷 115-137页

作者： Cohen, David Jeavons, Peter Jefferson, Christopher Petrie, Karen E. Smith, Barbara M. Natl Univ Ireland Univ Coll Cork Cork Constraint Computat Ctr Cork Ireland Univ London Royal Holloway Dept Comp Sci London England Univ Oxford Comp Lab Oxford OX1 3QD England Univ St Andrews Sch Comp Sci St Andrews KY16 9AJ Fife Scotland

We review the many different definitions of symmetry for constraint satisfaction problems (CSPs) that have appeared in the literature, and show that a symmetry can be defined in two fundamentally different ways: as an operation preserving the solutions of a CSP instance, or else as an operation preserving the constraints. We refer to these as solution symmetries and constraint symmetries. We define a constraint symmetry more precisely as an automorphism of a hypergraph associated with a CSP instance, the microstructure complement. We show that the solution symmetries of a CSP instance can also be obtained as the automorphisms of a related hypergraph, the k-ary nogood hypergraph and give examples to show that some instances have many more solution symmetries than constraint symmetries. Finally, we discuss the practical implications of these different notions of symmetry.

关键词： constraint satisfaction problems symmetry

来源：评论

学校读者我要写书评

暂无评论

Applying ad-hoc global constraints with the case constraint to still-life

Applying ad-hoc global constraints with the case constraint ...

引用

11th international conference on principles and practice of constraint programming (cp 2005)

作者： Cheng, Kenil C. K. Yap, Roland H. C. Natl Univ Singapore Sch Comp Singapore 117548 Singapore

the Still-Life problem is challenging for cp techniques because the basic constraints of the game of Life are loose and give poor propagation for Still-Life. In this paper, we show how ad hoc global case constraints can be customized to construct various models to provide much stronger propagation with cp solvers. Since we use custom ad hoc constraints of high arity where the number of tuples to define the constraint are large, the actual constraint representation becomes important to avoid excessive space consumption. We demonstrate how to use BDDs to construct good representations for the case constraint which is critical for efficiency. Our results seem comparable to hybrid cp/IP models even though we are only using propagation albeit on ad hoc global constraints. this paper shows an extensive example of how to systematically build models using different kinds of ad hoc constraints. It also demonstrates the solving potential of ad hoc global constraints.

关键词： modeling binary decision diagram still-life problem ad-hoc constraint non-binary constraint

来源：评论

学校读者我要写书评

暂无评论

Generating Special-Purpose Stateless Propagators for Arbitrary constraints

Generating Special-Purpose Stateless Propagators for Arbitra...

引用

16th Annual international conference on the principles and practice of constraint programming

作者： Gent, Ian P. Jefferson, Chris Miguel, Ian Nightingale, Peter Univ St Andrews Sch Comp Sci St Andrews Fife Scotland

ISBN: (纸本)9783642153952

Given an arbitrary constraint a on 71 variables with domain size d, we show how to generate a custom propagator that establishes GAC in time O(nd) by precomputing the propagation that would be performed on every reachable subdomain of scope(c). Our propagators are stateless: they store no state between calls, and so incur no overhead in storing and backtracking state during search. the preprocessing step can take exponential time and the custom propagator is potentially exponential in size. However, for small constraints used repeatedly, in one problem or many, this technique can provide substantial practical gains. Our experimental results show that, compared with optimised implementations of the table constraint;this technique can lead to an order of magnitude speedup;while doing identical search on realistic problems. the technique can also be many times faster than a decomposition into primitive constraints in the Minion solver. Propagation is so fast that, for constraints available in our solver, the generated propagator compares well with a human-optimised propagator for the same constraint.

关键词： constraint theory

来源：评论

学校读者我要写书评

暂无评论

Efficient Methods for constraint Acquisition 1

引用

24th international conference on the principles and practice of constraint programming (cp)

作者： Tsouros, Dimosthenis C. Stergiou, Kostas Sarigiannidis, Panagiotis G. Univ Western Macedonia Dept Informat & Telecommun Engn Kozani Greece

ISBN: (数字)9783319983349

ISBN: (纸本)9783319983349;9783319983332

constraint acquisition systems such as QuAcq and MultiAcq can assist non-expert users to model their problems as constraint networks by classifying (partial) examples as positive or negative. For each negative example, the former focuses on one constraint of the target network, while the latter can learn a maximum number of constraints. Two bottlenecks of the acquisition process where both these algorithms encounter problems are the large number of queries required to reach convergence, and the high cpu times needed to generate queries, especially near convergence. We propose methods that deal with both these issues. the first one is an algorithm that blends the main idea of MultiAcq into QuAcq resulting in a method that learns as many constraints as MultiAcq does after a negative example, but with a lower complexity. the second is a technique that helps reduce the number of queries significantly. the third is based on the use of partial queries to cut down the time required for convergence. Experiments demonstrate that our resulting algorithm, which integrates all the new techniques, does not only generate considerably fewer queries than QuAcq and MultiAcq, but it is also by far faster than both of them, both in average query generation time and in total run time.

关键词： constraint acquisition Learning Modeling

来源：评论

学校读者我要写书评

暂无评论

OWL: A description logic based ontology language

引用

11th international conference on principles and practice of constraint programming (cp 2005)

作者： Horrocks, I Univ Manchester Sch Comp Sci Manchester M13 9PL Lancs England

ISBN: (纸本)3540292381

Description Logics (DLs) are a family of class (concept) based knowledge representation formalisms. they are characterised by the use of various constructors to build complex concepts from simpler ones, an emphasis on the decidability of key reasoning tasks, and by the provision of sound, complete and (empirically) tractable reasoning services. Although they have a range of applications (e.g., reasoning with database schemas and queries [1,2]), DLs are perhaps best known as the basis for ontology languages such as OIL, DAML+OIL and OWL [3]. the decision to base these languages 011 DLs was motivated by a requirement not only that key inference problems (such as class satisfiability and subsumption) be decidable, but that "practical" decision procedures and "efficient" implemented systems also be available. that DLs were able to meet the above requirements was the result of extensive research within the DL community over the course of the preceding 20 years or more. this research mapped out a complex landscape of languages, exploring a range of different language constructors, studying the effects of various combinations of these constructors on decidability and worst case complexity, and devising At the same time, work on implementation and optimisation techniques demonstrated that, in spite of the high worst case complexity of key inference problems (usually at least ExpTime), highly optimised DL systems were capable of providing practical reasoning support in the typical cases encountered in realistic applications [4]. With the added impetus provided by the OWL standardisation effort, DL systems are now being used to provide computational services for a rapidly expanding range of ontology tools and applications [5-9]. © Springer-Verlag Berlin Heidelberg 2005.

关键词： Formal languages

来源：评论

学校读者我要写书评

暂无评论

Improved algorithms for max-restricted path consistency

引用

9th international conference on principles and practice of constraint programming, cp 2003

作者： Grandoni, Fabrizio Italiano, Giuseppe F. Dipartimento di Informatica Sistemi e Produzione Università di Roma "Tor Vergata" Via del Politecnico 1 Roma00133 Italy

ISBN: (纸本)3540202021

A binary constraints network consists of a set of n variables, defined on domains of size at most d, and a set of e binary constraints. the binary constraint satisfaction problem consists in finding a solution for a binary constraints network, that is an instantiation of all the variables which satisfies all the constraints. A value a in the domain of variable x is inconsistent if there is no solution which assigns a to x. Many filtering techniques have been proposed to filter out inconsistent values from the domains. Most of them are based on enforcing a given kind of local consistency. One of the most important such consistencies is max-restricted path consistency. the fastest algorithm to enforce maxrestricted path consistency has a O(end3) time complexity and a O(end) space complexity. In this paper we present two improved algorithms for the same problem. the first still has a O(end3) time complexity, but it reduces the space usage to O(ed). the second improves the time complexity to O(end2.575), and has a O(end2) space complexity. © Springer-Verlag Berlin Heidelberg 2003.

关键词： constraint satisfaction problems

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：