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

26th international conference on principles and practice of constraint programming, cp 2020

作者： Fichte, Johannes K. Hecher, Markus Szeider, Stefan School of Engineering Sciences TU Dresden Dresden Germany Database and Artificial Intelligence Group TU Wien Vienna Austria Algorithms and Complexity Group TU Wien Vienna Austria

ISBN: (纸本)9783030584740

Bounded fractional hypertree width is the most general known structural property that guarantees polynomial-time solvability of the constraint satisfaction problem. Fichte et al. (cp 2018) presented a robust and scalable method for finding optimal fractional hypertree decompositions, based on an encoding to SAT Modulo theory (SMT). In this paper, we provide an in-depth study of two powerful symmetry breaking predicates that allow us to further speed up the SMT-based decomposition: RootClique fixes the root of the decomposition tree;LexTopSort fixes the elimination ordering with respect to an underlying DAG. We perform an extensive empirical evaluation of both symmetry-breaking predicates with respect to the primal graph (which is known in advance) and the induced graph (which is generated during the search). © 2020, Springer Nature Switzerland AG.

关键词： constraint satisfaction problems

来源：评论

学校读者我要写书评

暂无评论

17th international conference on principles and practice of constraint programming, cp 2011

17th International Conference on Principles and Practice of ...

引用

17th international conference on principles and practice of constraint programming, cp 2011

ISBN: (纸本)9783642237850

the proceedings contain 61 papers. the special focus in this conference is on principles and practice of constraint programming. the topics include: Neuron constraints to model complex real-world problems;A constraint based approach to cyclic RcpSP;an efficient light solver for querying the semantic web;on guaranteeing polynomially bounded search tree size;a framework for decision-based consistencies;Hierarchically nested convex VCSP;tractable triangles;on minimal weighted clones;Solving MAXSAT by solving a sequence of simpler SAT instances;operations research and constraint programming at google;filtering algorithms for discrete cumulative problems with overloads of resource;Synthesis of search algorithms from high-level cp models;revisiting the tree constraint;half reification and flattening;the parameterized complexity of local consistency;symmetry breaking in numeric constraint problems;on minimal constraint networks;structural tractability of constraint optimization;models and strategies for variants of the job shop scheduling problem;MaxRPC algorithms based on bitwise operations;Solving problems with cp: Four common pitfalls to avoid;Grid-based SAT solving with iterative partitioning and clause learning;large neighborhood search for dial-a-ride problems;On deciding MUS membership with QBF;On the relative efficiency of DPLL and OBDDs with axiom and join;Min CSP on four elements: Moving beyond submodularity;algorithm selection and scheduling;incorporating variance in impact-based search;a quadratic edge-finding filtering algorithm for cumulative resource constraints;A CSP solver focusing on FAC variables;constraint reasoning and kernel clustering for pattern decomposition with scaling;a constraint seeker: Finding and ranking global constraints from examples;solving qualitative constraints involving landmarks;search combinators.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Integration of Structural constraints into TSP Models 25th

Integration of Structural Constraints into TSP Models

引用

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

作者： Isoart, Nicolas Regin, Jean-Charles Univ Cote Azur CNRS I3S Sophia Antipolis France

ISBN: (纸本)9783030300487

Several models based on constraint programming have been proposed to solve the traveling salesman problem (TSP). the most efficient ones, such as the weighted circuit constraint (WCC), mainly rely on the Lagrangian relaxation of the TSP, based on the search for spanning tree or more precisely "1-tree". the weakness of these approaches is that they do not include enough structural constraints and are based almost exclusively on edge costs. the purpose of this paper is to correct this drawback by introducing the Hamiltonian cycle constraint associated with propagators. We propose some properties preventing the existence of a Hamiltonian cycle in a graph or, conversely, properties requiring that certain edges be in the TSP solution set. Notably, we design a propagator based on the research of k-cutsets. the combination of this constraint with the WCC constraint allows us to obtain, for the resolution of the TSP, gains of an order of magnitude for the number of backtracks as well as a strong reduction of the computation time.

关键词： Global constraint TSP Propagator

来源：评论

学校读者我要写书评

暂无评论

Augmenting Stream constraint programming with Eventuality Conditions 1

引用

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

作者： Lee, Jasper C. H. Lee, Jimmy H. M. Zhong, Allen Z. Brown Univ Dept Comp Sci Providence RI 02912 USA Chinese Univ Hong Kong Dept Comp Sci & Engn Shatin Hong Kong Peoples R China

ISBN: (数字)9783319983349

ISBN: (纸本)9783319983349;9783319983332

Stream constraint programming is a recent addition to the family of constraint programming frameworks, where variable domains are sets of infinite streams over finite alphabets. Previous works showed promising results for its applicability to real-world planning and control problems. In this paper, motivated by the modelling of planning applications, we improve the expressiveness of the framework by introducing (1) the "until" constraint, a new construct that is adapted from Linear Temporal Logic and (2) the @ operator on streams, a syntactic sugar for which we provide a more efficient solving algorithm over simple desugaring. For both constructs, we propose corresponding novel solving algorithms and prove their correctness. We present competitive experimental results on the Missionaries and Cannibals logic puzzle and a standard path planning application on the grid, by comparing with Apt and Brand's method for verifying eventuality conditions using a cp approach.

关键词： Motion planning

来源：评论

学校读者我要写书评

暂无评论

Generalized support and formal development of constraint propagators

引用

AI COMMUNICATIONS 2017年第5期30卷 325-346页

作者： Caldwell, James Gent, Ian P. Nightingale, Peter Univ Wyoming Dept Comp Sci 1000 E Univ Ave Laramie WY 82071 USA Univ St Andrews Sch Comp Sci St Andrews KY16 9SX Fife Scotland

constraint programming is a family of techniques for solving combinatorial problems, where the problem is modelled as a set of decision variables (typically with finite domains) and a set of constraints that express relations among the decision variables. One key concept in constraint programming is propagation: reasoning on a constraint or set of constraints to derive new facts, typically to remove values from the domains of decision variables. Specialized propagation algorithms (propagators) exist for many classes of constraints. the concept of support is pervasive in the design of propagators. Traditionally, when a domain value ceases to have support, it may be removed because it takes part in no solutions. Arc-consistency algorithms such as AC2001 [in: Proceedings 17th international Joint conference on Artificial Intelligence (IJCAI 2001), 2001, pp. 309-315] make use of support in the form of a single domain value. GAC algorithms such as GAC-Schema [in: Proceedings 15th international Joint conference on Artificial Intelligence (IJCAI 97), 1997, pp. 398-404] use a tuple of values to support each literal. We generalize these notions of support in two ways. First, we allow a set of tuples to act as support. Second, the supported object is generalized from a set of literals (GAC-Schema) to an entire constraint or any part of it. We design a methodology for developing correct propagators using generalized support. A constraint is expressed as a family of support properties, which may be proven correct against the formal semantics of the constraint. We show how to derive correct propagators from the constructive proofs of the support properties. the framework is carefully designed to allow efficient algorithms to be produced. Derived algorithms may make use of dynamic literal triggers or watched literals [in: Proc. 12th international conference on the principles and practice of constraint programming (cp 2006), 2006, pp. 182-197] for efficiency. Finally, three case st

关键词： constraint satisfaction problem constraint programming formal methods

来源：评论

学校读者我要写书评

暂无评论

Rotation-Based Formulation for Stable Matching 23rd

Rotation-Based Formulation for Stable Matching

引用

33rd international conference on Logic programming / 23rd international conference on principles and practice of constraint programming (cp) / 20th international conference on theory and Applications of Satisfiability Testing (SAT)

作者： Siala, Mohamed O'Sullivan, Barry Univ Coll Cork Insight Ctr Data Analyt Dept Comp Sci Cork Ireland

ISBN: (纸本)9783319661582;9783319661575

We introduce new cp models for the many-to-many stable matching problem. We use the notion of rotation to give a novel encoding that is linear in the input size of the problem. We give extra filtering rules to maintain arc consistency in quadratic time. Our experimental study on hard instances of sex-equal and balanced stable matching shows the efficiency of one of our propositions as compared with the state-of-the-art constraint programming approach.

关键词： constraint theory

来源：评论

学校读者我要写书评

暂无评论

NECESSARY CONDITIONS FOR TRACTABILITY OF VALUED CSPs

引用

SIAM JOURNAL ON DISCRETE MAthEMATICS 2015年第4期29卷 2361-2384页

作者： thapper, Johan Zivny, Stanislav Univ Paris Est F-77454 Paris France Univ Oxford Dept Comp Sci Oxford OX1 3QD England

the connection between constraint languages and clone theory has been a fruitful line of research on the complexity of constraint satisfaction problems. In a recent result, Cohen et al. [SIAM J. Comput., 42 (2013), pp. 915-1939] have characterized a Galois connection between valued constraint languages and so-called weighted clones. In this paper, we study the structure of weighted clones. We extend the results of Creed and. Zivny from [Proceedings of the 17th international conference on principles and practice of constraint programming, 2011, pp. 210-224] on types of weightings necessarily contained in every nontrivial weighted clone. this result has immediate computational complexity consequences as it provides necessary conditions for tractability of weighted clones and thus valued constraint languages. We demonstrate that some of the necessary conditions are also sufficient for tractability, while others are provably not.

关键词： discrete optimization valued constraint satisfaction problems weighted clones weighted polymorphisms

来源：评论

学校读者我要写书评

暂无评论

principles and practice of constraint programming, cp 2011 - 17th international conference, Proceedings

Principles and Practice of Constraint Programming, CP 2011 -...

引用

17th international conference on principles and practice of constraint programming, cp 2011

ISBN: (纸本)9783642237850

the proceedings contain 59 papers. the topics discussed include: orchestrating satisfiability engines;operations research and constraint programming at Google;a constraint seeker: finding and ranking global constraints from examples;bin repacking scheduling in virtualized datacenters;optimal carpet cutting;a hybrid approach for solving real-world nurse rostering problems;constraint programming for controller synthesis;neuron constraints to model complex real-world problems;an efficient light solver for querying the semantic web;on guaranteeing polynomially bounded search tree size;a framework for decision-based consistencies;tractable triangles;on minimal weighted clones;filtering algorithms for discrete cumulative problems with overloads of resource;revisiting the tree constraint;half reification and flattening;the parameterized complexity of local consistency;and symmetry breaking in numeric constraint problems.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Linking Prefixes and Suffixes for constraints Encoded Using Automata with Accumulators

Linking Prefixes and Suffixes for Constraints Encoded Using ...

引用

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

作者： Beldiceanu, Nicolas Carlsson, Mats Flener, Pierre Rodriguez, Maria Andreina Francisco Pearson, Justin CNRS INRIA TASC Team Mines Nantes F-44307 Nantes France SICS Kista 16429 Sweden Uppsala Univ Dept Informat Technol Uppsala 75105 Sweden

ISBN: (纸本)9783319104287;9783319104270

Consider a constraint on a sequence of variables functionally determining a result variable that is unchanged under reversal of the sequence. Most such constraints have a compact encoding via an automaton augmented with accumulators, but it is unknown how to maintain domain consistency efficiently for most of them. Using such an automaton for such a constraint, we derive an implied constraint between the result variables for a sequence, a prefix thereof, and the corresponding suffix. We show the usefulness of this implied constraint in constraint solving, both by local search and by propagation-based systematic search.

关键词： constraint theory

来源：评论

学校读者我要写书评

暂无评论

Solving Intensional Weighted CSPs by Incremental Optimization with BDDs

Solving Intensional Weighted CSPs by Incremental Optimizatio...

引用

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

作者： Bofill, Miquel Palahi, Miquel Suy, Josep Villaret, Mateu Univ Girona Dept Informat Matemat Aplicada & Estat Girona Spain

ISBN: (纸本)9783319104287;9783319104270

We present a method for solving weighted constraint Satisfaction Problems, based on translation into a constraint Optimization Problem and iterative calls to an SMT solver, with successively tighter bounds of the objective function. the novelty of the method herewith described lies in representing the bound constraint as a shared Binary Decision Diagram, which in turn is translated into SAT. this offers two benefits: first, BDDs built for previous bounds can be used to build the BDDs for new (tighter) bounds, considerably reducing the BDD construction time;second, as a by-product, many clauses asserted to the solver in previous iterations can be reused. the reported experimentation on the WSimply system shows that this technique has better performance in general than other methods implemented in the system. Moreover, with the new technique WSimply outperforms some state-of-the-art solvers in most of the studied instances.

关键词： constraint satisfaction problems

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：