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

Dynamic ordering for asynchronous backtracking on DisCSPs

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

作者： Zivan, Roie Meisels, Amnon Ben Gurion Univ Negev Dept Comp Sci IL-84105 Beer Sheva Israel

ISBN: (纸本)3540292381

An algorithm that performs asynchronous backtracking on distributed CSPs, with dynamic ordering of agents is proposed, ABT_DO. Agents propose reorderings of lower priority agents and send these proposals whenever they send assignment messages. Changes of ordering triggers a different computation of Nogoods. the dynamic ordered asynchronous backtracking algorithm uses polynomial space, similarly to standard ABT. the ABT_DO algorithm with three different ordering heuristics is compared to standard ABT on randomly generated DisCSPs. A Nogood-triggered heuristic, inspired by dynamic backtracking, is found to outperform static order ABT by a large factor in run-time and improve the network load.

关键词： distributed constraint satisfaction distributed AI search

来源：评论

学校读者我要写书评

暂无评论

constraint models for the covering test problem

Constraint models for the covering test problem

引用

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

作者： Hnich, Brahim Prestwich, Steven D. Selensky, Evgeny Smith, Barbara M. Izmir Univ Econ Fac Comp Sci Izmir Turkey Natl Univ Ireland Univ Coll Cork Cork Constraint Computat Ctr Cork Ireland Vidus Ltd Ipswich Suffolk England

Covering arrays can be applied to the testing of software, hardware and advanced materials, and to the effects of hormone interaction on gene expression. In this paper we develop constraint programming models of the problem of finding an optimal covering array. Our models exploit global constraints, multiple viewpoints and symmetry-breaking constraints. We show that compound variables, representing tuples of variables in our original model, allow the constraints of this problem to be represented more easily and hence propagate better. With our best integrated model, we are able to either prove the optimality of existing bounds or find new optimal solutions, for arrays of moderate size. Local search on a SAT-encoding of the model is able to find improved solutions and bounds for larger problems.

关键词： modelling covering arrays symmetry local search testing chanelling constraints global constraints

来源：评论

学校读者我要写书评

暂无评论

Symmetry breaking constraints for value symmetries in constraint satisfaction

引用

constraintS 2006年第2-3期11卷 221-267页

作者： Law, Y. C. Lee, J. H. M. Chinese Univ Hong Kong Dept Comp Sci & Engn Shatin Hong Kong Peoples R China

constraint satisfaction problems (CSPs) sometimes contain both variable symmetries and value symmetries, causing adverse effects on CSP solvers based on tree search. As a remedy, symmetry breaking constraints are commonly used. While variable symmetry breaking constraints can be expressed easily and propagated efficiently using lexicographic ordering, value symmetry breaking constraints are often difficult to formulate. In this paper, we propose two methods of using symmetry breaking constraints to tackle value symmetries. First, we show theoretically when value symmetries in one CSP correspond to variable symmetries in another CSP of the same problem. We also show when variable symmetry breaking constraints in the two CSPs, combined using channeling constraints, are consistent. Such results allow us to tackle value symmetries efficiently using additional CSP variables and channeling constraints. Second, we introduce value precedence, a notion which can be used to break a common class of value symmetries, namely symmetries of indistinguishable values. While value precedence can be expressed using inefficient if-then constraints in existing CSP solvers, we propose efficient propagation algorithms for implementing global value precedence constraints. We also characterize several theoretical properties of the value precedence constraints. Extensive experiments are conducted to verify the feasibility and efficiency of the two proposals.

关键词： symmetry breaking value symmetries constraint satisfaction

来源：评论

学校读者我要写书评

暂无评论

Symmetry definitions for constraint satisfaction problems

引用

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

作者： 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

ISBN: (纸本)3540292381

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

来源：评论

学校读者我要写书评

暂无评论

Tools and Algorithms for the Construction and Analysis of Systems - 12th international conference, TACAS 2006. Held as Part of the Joint European conferences on theory and practice of Software, ETAPS 2006, Proceedings

引用

12th international conference on Tools and Algorithms for the Construction and Analysis of Systems, TACAS 2006. Held as Part of the Joint European conferences on theory and practice of Software, ETAPS 2006

ISBN: (纸本)3540330569

the proceedings contain 33 papers. the topics discussed include: weighted pushdown systems and trust management systems;automatic verification of parameterized data structures;parameterized verification of π calculus systems;easy parameterized verification of biphase mark and 8N1 protocols;evaluating the effectiveness of slicing for model reduction of concurrent object oriented programs;new metrics for static variable ordering in decision diagrams;widening ROBDDs with prime implicants;efficient guided symbolic reachability using reachability expressions;SAT - based software certification;exploration of the capabilities of constraint programming for software verification;efficient abstraction refinement in interpolation based unbounded model checking;and approximating predicate images for bit vector logic.

关键词： Computer software

来源：评论

学校读者我要写书评

暂无评论

the impact of search heuristics on heavy-tailed behaviour

引用

constraintS 2006年第2-3期11卷 159-178页

作者： Hulubei, Tudor O'Sullivan, Barry Natl Univ Ireland Univ Coll Cork Dept Comp Sci Cork Constraint Computat Ctr Cork Ireland

the heavy-tailed phenomenon that characterises the runtime distributions of backtrack search procedures has received considerable attention over the past few years. Some have conjectured that heavy-tailed behaviour is largely due to the characteristics of the algorithm used. Others have conjectured that problem structure is a significant contributor. In this paper we attempt to explore the former hypothesis, namely we study how variable and value ordering heuristics impact the heavy-tailedness of runtime distributions of backtrack search procedures. We demonstrate that heavy-tailed behaviour can be eliminated from particular classes of random problems by carefully selecting the search heuristics, even when using chronological backtrack search. We also show that combinations of good search heuristics can eliminate heavy tails from quasigroups with holes of order 10 and 20, and give some insights into why this is the case. these results motivate a more detailed analysis of the effects that variable and value orderings can have on heavy-tailedness. We show how combinations of variable and value ordering heuristics can result in a runtime distribution being inherently heavy-tailed. Specifically, we show that even if we were to use an oracle to refute insoluble subtrees optimally, for some combinations of heuristics we would still observe heavy-tailed behaviour. Finally, we study the distributions of refutation sizes found using different combinations of heuristics and gain some further insights into what characteristics tend to give rise to heavy-tailed behaviour.

关键词： search heuristics constraint satisfactions runtime distributions

来源：评论

学校读者我要写书评

暂无评论

Symmetry breaking constraints for value symmetries in constraint satisfaction

Symmetry breaking constraints for value symmetries in constr...

引用

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

作者： Law, Y. C. Lee, J. H. M. Chinese Univ Hong Kong Dept Comp Sci & Engn Shatin Hong Kong Peoples R China

关键词： symmetry breaking value symmetries constraint satisfaction

来源：评论

学校读者我要写书评

暂无评论

the impact of search heuristics on heavy-tailed behaviour

The impact of search heuristics on heavy-tailed behaviour

引用

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

作者： Hulubei, Tudor O'Sullivan, Barry Natl Univ Ireland Univ Coll Cork Dept Comp Sci Cork Constraint Computat Ctr Cork Ireland

关键词： search heuristics constraint satisfactions runtime distributions

来源：评论

学校读者我要写书评

暂无评论

Specialised constraints for stable matching problems

引用

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

作者： Unsworth, C Prosser, P Univ Glasgow Dept Comp Sci Glasgow G12 8QQ Lanark Scotland

ISBN: (纸本)3540292381

the stable marriage problem (SM) and the Hospital / Residents problem (HR) are both stable matching problems. they consist of two sets of objects that need to be matched to each other;in SM men to women, and in HR residents to hospitals. Each set of objects expresses a ranked preference for the objects in the other set, in the form of a preference list. the problem is then to find a matching of one set to the other such that the matching is stable. A matching is stable iff it contains no blocking pairs. A blocking pair in a matching M consists of two objects x and y one from each set(x = man and y = woman for SM or x = hospital and y = resident in HR), such that x and y are not matched in M and both x and y would rather be matched to each other than to there assignment in M. Algorithms have been published for both of these problems and optimal constraint models have been published for the stable marriage problem. So the main question would be why the need for specialised constraint for these problems? the SM algorithm and the optimal constraint encodings all have a time complexity of O(n²), but in practice it can take over a minute for the constraint models to find a solution to a problem of size 45 while the SM algorithm can find a solution in less than two hundredths of a second. there have not been any optimal HR constraint models published, but I assume the same performance gap would exist. the advantage of the constraint solutions are their versatility. Many harder valiants of the stable matching problems can be solved by adding simple side constraints to the existing;models, this is not possible with the matching algorithms. So the motivation behind a specialised constraint is to try and combine the efficiency of the algorithm with the versatility of the constraint models. In the full version of this paper I discuss issues concerning the creation of specialised constraints to solve these problems. I then go on to present some empirical results that

关键词： constraint theory

来源：评论

学校读者我要写书评

暂无评论

Leveraging the learning power of examples in automated constraint acquisition

引用

10th international conference on principles and practice of constraint programming, cp 2004

作者： Bessiere, Christian Coletta, Remi Freuder, Eugene C. O’Sullivan, Barry 161 rue Ada Montpellier Cedex 534392 France Cork Constraint Computation Centre Department of Computer Science University College Cork Ireland

ISBN: (纸本)3540232419

constraint programming is rapidly becoming the technology of choice for modeling and solving complex combinatorial problems. However, users of constraint programming technology need significant expertise in order to model their problem appropriately. the lack of availability of such expertise can be a significant bottleneck to the broader uptake of constraint technology in the real world. In this paper we are concerned with automating the formulation of constraint satisfaction problems from examples of solutions and non-solutions. We combine techniques from the fields of machine learning and constraint programming. In particular we present a portfolio of approaches to exploiting the semantics of the constraints that we acquire to improve the efficiency of the acquisition process. We demonstrate how inference and search can be used to extract useful information that would otherwise be hidden in the set of examples from which we learn the target constraint satisfaction problem. We demonstrate the utility of the approaches in a case-study domain. © Springer-Verlag Berlin Heidelberg 2004.

关键词： constraint satisfaction problems

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：