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

20th international conference on the principles and practice of constraint programming, cp 2014

作者： Nguyen, thi-Van-Anh Lallouet, Arnaud GREYC Université de Caen Campus Côte de Nacre Boulevard du Maréchal Juin BP 5186 14032 Caen Cedex France

ISBN: (纸本)9783319104270

Game theory studies situations in which multiple agents having conflicting objectives have to reach a collective decision. the question of a compact representation language for agents utility function is of crucial importance since the classical representation of a n-players game is given by a n-dimensional matrix of exponential size for each player. In this paper we use the framework of constraint Games in which CSP are used to represent utilities. constraint programming -including global constraints- allows to easily give a compact and elegant model to many useful games. constraint Games come in two flavors: constraint Satisfaction Games and constraint Optimization Games, the first one using satisfaction to define boolean utilities. In addition to multimatrix games, it is also possible to model more complex games where hard constraints forbid certain situations. In this paper we study complete search techniques and show that our solver using the compact representation of constraint Games is faster than the classical game solver Gambit by one to two orders of magnitude. © 2014 Springer international Publishing Switzerland.

关键词： Constrained optimization

来源：评论

学校读者我要写书评

暂无评论

principles and practice of constraint programming – cp 2010 1

引用

丛书名： Lecture Notes in Computer Science

1000年

作者： David Cohen

ISBN: (数字)9783642153969

ISBN: (纸本)9783642153952

the 16th annual international conference on the principles and practice of constraint programming (cp 2010) was held in St. Andrews, Scotland, during September 6–10, 2010. We would like to thank our sponsors for their generous support of this event. this conference is concerned with all aspects of computing with constraints, including:theory,algorithms,applications,environments,languages,modelsand systems. We received a wide variety of submissions, each of which was reviewed by at least three referees. Referees were chosen for each submission by an initial bidding process where Program Committee members chose papers from their area of interest. the range of expertise represented by the large Program C- mittee meant that almost all submissions were reviewed by subject experts on the Program Committee, or by colleagues chosen by members of the Program Committee for their particular expertise. Papers weresolicitedeither as long (15 page), or short (8 page) submissions. Short-paper submissions were refereed to exactly the same high standards as long-paper submissions but naturally were expected to contain a smaller quantity of new material. thus there is no disti- tion in these proceedings between short and long papers. I used the excellent EasyChair conference management system to support this process of reviewing, and for the collation and organization of these proceedings. Submissions were made either to the applications track or to the research track. therewere101(23short)researchtracksubmissionsofwhich36(8short) wereaccepted,whichisa36%(35%ofshort)acceptancerate. Applicationstrack submissions received special consideration and the acceptance rate was sign- cantly higher than for the research track.

关键词： Software Engineering/programming and Operating Systems programming Techniques programming Languages, Compilers, Interpreters Algorithm Analysis and Problem Complexity Mathematical Logic and Formal Languages Logics and Meanings of Programs

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Solving minimal constraint networks in qualitative spatial and temporal reasoning

Solving minimal constraint networks in qualitative spatial a...

引用

18th international conference on principles and practice of constraint programming, cp 2012

作者： Liu, Weiming Li, Sanjiang Centre for Quantum Computation and Intelligent Systems Faculty of Engineering and Information Technology University of Technology Sydney Australia

ISBN: (纸本)9783642335570

the minimal label problem (MLP) (also known as the deductive closure problem) is a fundamental problem in qualitative spatial and temporal reasoning (QSTR). Given a qualitative constraint network Γ, the minimal network of Γ relates each pair of variables (x,y) by the minimal label of (x,y), which is the minimal relation between x,y that is entailed by network Γ. It is well-known that MLP is equivalent to the corresponding consistency problem with respect to polynomial Turing-reductions. this paper further shows, for several qualitative calculi including Interval Algebra and RCC-8 algebra, that deciding the minimality of qualitative constraint networks and computing a solution of a minimal constraint network are both NP-hard problems. © 2012 Springer-Verlag.

关键词： Algebra

来源：评论

学校读者我要写书评

暂无评论

PLASMA: A constraint based planning architecture

引用

10th international conference on the principles and practice of constraint programming

作者： Bachmann, A Bedrax-Weiss, T Frank, J Iatauro, M McGann, C Taylor, W NASA Computat Sci Div Ames Res Ctr Moffett Field CA 94035 USA

ISBN: (纸本)3540232419

Until recently, planning research focused on solving problems of feasibility using models consisting of causal rules. Propositional logic is sufficient for representing such rules. However, many planning problems also contain time and resource constraints. It is often impractical to represent such planning domains with propositions. Large time horizons and possible resource states lead to enormous domain representations. Propositional representations can often obscure information that is useful during search. Finally, propositional representations can make it difficult for human modelers to express the domain in a convenient and natural way. the constraint-based Planning paradigm employs constraints as the building blocks of both planning domain rules and plans. the building blocks of such plans are intervals of time over which some state holds or an action occurs in a plan. Each interval is represented by variables describing its properties (e.g. start, end, duration). At each step of the planning process, a mapping is maintained between the plan under construction and an underlying constraint network. As actions are added to the plan, constraints are posted on variables representing the action, its preconditions and its effects (a generalization of causal links). the domain rules contain directives for adding new intervals and for posting constraints over the variables on those intervals as plans are modified. Employing constraints in rules makes it easy to represent disjunctive preconditions, conditional effects, and mutual exclusions directly. the semantics of this mapping ensure that logical inference (e.g. propagation) on the constraint network can be used directly by search engines operating on plans.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Computing explanations for global scheduling constraints

引用

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

作者： Vilím, Petr Charles University Malostranské náměstí 2/25 Praha 1 Czech Republic

ISBN: (纸本)3540202021

Integration of explanations into a CSP solver is a technique addressing difficult question "why my problem has no solution". Besides providing some sort of answer to the user, explanations can be used for debugging, solving dynamic problems and in advanced search algorithms. Explanations work pretty well with simple constraints. However, in order to use explanations together with a global constraint, its filtering algorithm (i.e. propagation) has to be enhanced to be explanation-aware. In my work I focus on such a technique for classical scheduling filtering algorithms like edge-finding and not-first/not-last. © Springer-Verlag Berlin Heidelberg 2003.

关键词： constraint satisfaction problems

来源：评论

学校读者我要写书评

暂无评论

Preprocessing techniques for distributed constraint optimization

引用

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

作者： Ali, Syed Muhammad Koenig, Sven Tambe, Milind USC CS Department 941 W 37th Street Los AngelesCA90089-0781 United States

ISBN: (纸本)3540232419

Although algorithms for Distributed constraint Optimization Problems (DCOPs) have emerged as a key technique for distributed reasoning, their application faces significant hurdles in many multiagent domains due to their inefficiency. Preprocessing techniques have been successfully used to speed up algorithms for centralized constraint satisfaction problems. this paper introduces a framework of very different preprocessing techniques that speed up ADOPT, an asynchronous optimal DCOP algorithm that significantly outperforms competing DCOP algorithms by more than one order of magnitude. © Springer-Verlag Berlin Heidelberg 2004.

关键词： constraint satisfaction problems

来源：评论

学校读者我要写书评

暂无评论

An algebraic approach to multi-sorted constraints

引用

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

作者： Bulatov, Andrei A. Jeavons, Peter Computing Laboratory University of Oxford United Kingdom

ISBN: (纸本)3540202021

Most previous theoretical study of the complexity of the constraint satisfaction problem has considered a simplified version of the problem in which all variables have the same domain. We show here that this apparently minor simplification can in fact change the complexity of the problem, and hence mask the existence of certain tractable constraint types. In this paper we describe a new algebraic framework which allows us to deal more precisely with problems where different variables may have different domains. Using this new framework we are able to identify new tractable classes of constraints, by combining algorithms devised for the simplified, single domain, problem. We also systematically develop an algebraic structural theory for the general problem, and show that this theory can be used to generalise earlier results about the complexity of certain constraint types. © Springer-Verlag Berlin Heidelberg 2003.

关键词： constraint satisfaction problems

来源：评论

学校读者我要写书评

暂无评论

Modelling chemical reactions using constraint programming and molecular graphs 10th

引用

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

作者： Wu, Christine Wei Cork Constraint Computation Center Department of Computer Science University College Cork Cork Ireland

ISBN: (纸本)3540232419

Generating all constitutional isomers (chemical compounds that have the same molecular formula but different chemical structures) is a challenging problem. the structures are normally represented by molecular graphs, where vertices are atoms and edges are chemical bonds. the degree of a vertex in the graph represents the valency of the corresponding atom. the problem can be extended to generating all sets of molecules that can result from a reaction. I have formulated this chemistry problem as a constraint satisfaction problem (CSP). As an initial representation of the problem, I represent each bond as a pair of variables. the atoms are represented by integers and connected by the bonds. the domain of each variable is all of the atoms in the problem. Each atom must appear a fixed number of times (its valency). For example, consider a problem that consists of two oxygens, two carbons and four hydrogens, i.e. eight atoms in three types. the number of bonds is half the sum of the atoms valencies. For the sample problem we need 8 bonds. It is easy to specify the valency constraint with help of the Ilog Solver constraint IloDistribute, which restricts the appearance of variables that take a given value in an array. We believe this is the first constraint encoding of the problem.

关键词：

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：