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

Towards Effective Deep Learning for constraint Satisfaction Problems 1

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

作者： Xu, Hong Koenig, Sven Kumar, T. K. Satish Univ Southern Calif Los Angeles CA 90089 USA

ISBN: (数字)9783319983349

ISBN: (纸本)9783319983349;9783319983332

Many attempts have been made to apply machine learning techniques to constraint satisfaction problems (CSPs). However, none of them have made use of the recent advances in deep learning. In this paper, we apply deep learning to predict the satisfiabilities of CSPs. To the best of our knowledge, this is the first effective application of deep learning to CSPs that yields >99.99% prediction accuracy on random Boolean binary CSPs whose constraint tightnesses or constraint densities do not determine their satisfiabilities. We use a deep convolutional neural network on a matrix representation of CSPs. Since it is NP-hard to solve CSPs, labeled data required for training are in general costly to produce and are thus scarce. We address this issue using the asymptotic behavior of generalized Model A, a new random CSP generation model, along with domain adaptation and data augmentation techniques for CSPs. We demonstrate the effectiveness of our deep learning techniques using experiments on random Boolean binary CSPs. While these CSPs are known to be in P, we use them for a proof of concept.

关键词： constraint satisfaction problems

来源：评论

学校读者我要写书评

暂无评论

An SMT Approach to Fractional Hypertree Width 1

引用

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

作者： Fichte, Johannes K. Hecher, Markus Lodha, Neha Szeider, Stefan Tech Univ Dresden Int Ctr Computat Log Dresden Germany TU Wien Database & Artificial Intelligence Grp Vienna Austria TU Wien Algorithms & Complex Grp Vienna Austria

ISBN: (数字)9783319983349

ISBN: (纸本)9783319983349;9783319983332

Bounded fractional hypertree width (fhtw) is the most general known structural property that guarantees polynomial-time solvability of the constraint satisfaction problem. Bounded fhtw generalizes other structural properties like bounded induced width and bounded hypertree width. We propose, implement and test the first practical algorithm for computing the fhtw and its associated structural decomposition. We provide an extensive empirical evaluation of our method on a large class of benchmark instances which also provides a comparison with known exact decomposition methods for hypertree width. Our approach is based on an efficient encoding of the decomposition problem to SMT (SAT modulo theory) with Linear Arithmetic as implemented in the SMT solver Z3. the encoding is further strengthened by preprocessing and symmetry breaking methods. Our experiments show (i) that fhtw can indeed be computed exactly for a wide range of benchmark instances, and (ii) that state-of-the art SMT techniques can be successfully applied for structural decomposition.

关键词： constraint satisfaction problems

来源：评论

学校读者我要写书评

暂无评论

A Large Neighboring Search Schema for Multi-agent Optimization 1

引用

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

作者： Hoang, Khoi D. Fioretto, Ferdinando Yeoh, William Pontelli, Enrico Zivan, Roie Washington Univ St Louis MO 63110 USA Univ Michigan Ann Arbor MI 48109 USA New Mexico State Univ Las Cruces NM 88003 USA Ben Gurion Univ Negev Beer Sheva Israel

ISBN: (数字)9783319983349

ISBN: (纸本)9783319983349;9783319983332

the Distributed constraint Optimization Problem (DCOP) is an elegant paradigm for modeling and solving multi-agent problems which are distributed in nature, and where agents cooperate to optimize a global objective within the confines of localized communication. Since solving DCOPs optimally is NP-hard, recent effort in the development of DCOP algorithms has focused on incomplete methods. Unfortunately, many of such proposals do not provide quality guarantees or provide a loose quality assessment. thus, this paper proposes the Distributed Large Neighborhood Search (DLNS), a novel iterative local search framework to solve DCOPs, which provides guarantees on solution quality refining lower and upper bounds in an iterative process. Our experimental analysis of DCOP benchmarks on several important classes of graphs illustrates the effectiveness of DLNS in finding good solutions and tight upper bounds in both problems with and without hard constraints.

关键词： Multiagent Systems Distributed constraint Optimization Large Neighborhood Search

来源：评论

学校读者我要写书评

暂无评论

An Incremental SAT-Based Approach to Reason Efficiently on Qualitative constraint Networks 1

引用

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

作者： Glorian, Gael Lagniez, Jean-Marie Montmirail, Valentin Sioutis, Michael Artois Univ CRIL F-62300 Lens France CNRS F-62300 Lens France Orebro Univ MPI AASS Orebro Sweden

ISBN: (数字)9783319983349

ISBN: (纸本)9783319983349;9783319983332

the RCC8 language is a widely-studied formalism for describing topological arrangements of spatial regions. Two fundamental reasoning problems that are associated with RCC8 are the problems of satisfiability and realization. Given a qualitative constraint network (QCN) of RCC8, the satisfiability problem is deciding whether it is possible to assign regions to the spatial variables of the QCN in such a way that all of its constraints are satisfied (solution). the realization problem is producing an actual spatial model that can serve as a solution. Researchers in RCC8 focus either on symbolically checking the satisfiability of a QCN or on presenting a method to realize (valuate) a satisfiable QCN. To the best of our knowledge, a combination of those two lines of research has not been considered in the literature in a unified and homogeneous approach, as the first line deals with native constraint-based methods, and the second one with rich mathematical structures that are difficult to implement. In this article, we combine the two aforementioned lines of research and explore the opportunities that surface by interrelating the corresponding reasoning problems, viz., the problems of satisfiability and realization. We restrict ourselves to QCNs that, when satisfiable, are realizable with rectangles. In particular, we propose an incremental SAT-based approach for providing a framework that reasons about the RCC8 language in a counterexample-guided manner. the incrementality of our approach also avoids the usual blow-up and the lack of scalability in SAT-based encodings. Specifically, our SAT-translation is parsimonious, i.e, constraints are added incrementally in a manner that guides the embedded SAT-solver and forbids it to find the same counter-example twice. We experimentally evaluated our approach and studied its scalability against state-of-the-art solvers for reasoning about RCC8 relations using a varied dataset of instances. the approach scales up and is competiti

关键词： RCC Qualitative Spatial and Temporal Reasoning SAT CEGAR

来源：评论

学校读者我要写书评

暂无评论

PW-AC: Extending compact-table to enforce pairwise consistency on table constraints 24th

PW-AC: Extending compact-table to enforce pairwise consisten...

引用

24th international conference on the principles and practice of constraint programming, cp 2018

作者： Schneider, Anthony Choueiry, Berthe Y. Constraint Systems Laboratory University of Nebraska-Lincoln Lincoln United States

ISBN: (纸本)9783319983332

the Compact-Table (CT) algorithm is the current state-of-the-art algorithm for enforcing Generalized Arc Consistency (GAC) on table constraints during search. Recently, algorithms for enforcing Pairwise Consistency (PWC), which is strictly stronger than GAC, were shown to be advantageous for solving difficult problems. However, PWC algorithms can be costly in terms of cpU time and memory consumption. As a result, their overhead may offset the savings of search-space reduction. In this paper, we introduce PW-CT, an algorithm that modifies CT to enforce full PWC. We show that PW-CT avoids the high memory requirements of prior PWC algorithms and significantly reduces the time required to enforce PWC. © Springer Nature Switzerland AG 2018.

关键词： constraint theory

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Clingo goes linear constraints over reals and integers

引用

thEORY AND practice OF LOGIC programming 2017年第5-6期17卷 872-888页

作者： Janhunen, Tomi Kaminski, Roland Ostrowski, Max Schellhorn, Sebastian Wanko, Philipp Schaub, Torsten Aalto Univ Aalto Finland Univ Potsdam Potsdam Germany INRIA Rennes Rennes France

the recent series 5 of the Answer Set programming (ASP) system clingo provides generic means to enhance basic ASP with theory reasoning capabilities. We instantiate this framework with different forms of linear constraints and elaborate upon its formal properties. Given this, we discuss the respective implementations, and present techniques for using these constraints in a reactive context. More precisely, we introduce extensions to clingo with difference and linear constraints over integers and reals, respectively, and realize them in complementary ways. Finally, we empirically evaluate the resulting clingo derivatives clingo[dl] and clingo[lp] on common language fragments and contrast them to related ASP systems.

关键词： constraint Answer Set programming (CASP) Answer Set programming (ASP) constraint Processing (cp) theory Solving

来源：评论

学校读者我要写书评

暂无评论

Clingo goes linear constraints over reals and integers

Clingo goes linear constraints over reals and integers

引用

33rd international conference on Logic programming colocated with the 23rd international conference on principles and practice of constraint programming / 20th international conference on theory and Applications of Satisfiability Testing

作者： Janhunen, Tomi Kaminski, Roland Ostrowski, Max Schellhorn, Sebastian Wanko, Philipp Schaub, Torsten Aalto Univ Aalto Finland Univ Potsdam Potsdam Germany INRIA Rennes Rennes France

关键词： constraint Answer Set programming (CASP) Answer Set programming (ASP) constraint Processing (cp) theory Solving

来源：评论

学校读者我要写书评

暂无评论

Encoding Linear constraints into SAT

Encoding Linear Constraints into SAT

引用

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

作者： Abio, Ignasi Stuckey, Peter J. NICTA Victoria Lab Melbourne Vic Australia

ISBN: (纸本)9783319104287;9783319104270

Linear integer constraints are one of the most important constraints in combinatorial problems since they are commonly found in many practical applications. Typically, encoding linear constraints to SAT performs poorly in problems with these constraints in comparison to constraint programming (cp) or mixed integer programming (MIP) solvers. But some problems contain a mix of combinatoric constraints and linear constraints, where encoding to SAT is highly effective. In this paper we define new approaches to encoding linear constraints into SAT, by extending encoding methods for pseudo-Boolean constraints. Experimental results show that these methods are not only better than the state-of-the-art SAT encodings, but also improve on MIP and cp solvers on appropriate problems. Combining the new encoding with lazy decomposition, which during runtime only encodes constraints that are important to the solving process that occurs, gives a robust approach to many highly combinatorial problems involving linear constraints.

关键词： constraint programming

来源：评论

学校读者我要写书评

暂无评论

Discriminating Instance Generation for Automated constraint Model Selection

Discriminating Instance Generation for Automated Constraint ...

引用

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

作者： Gent, Ian P. Hussain, Bilal Syed Jefferson, Christopher Kotthoff, Lars Miguel, Ian Nightingale, Glenna F. Nightingale, Peter Univ St Andrews Sch Comp Sci St Andrews KY16 9AJ Fife Scotland INSIGHT Ctr Data Analyt Dublin Ireland

ISBN: (纸本)9783319104287;9783319104270

One approach to automated constraint modelling is to generate, and then select from, a set of candidate models. this method is used by the automated modelling system CONJURE. To select a preferred model or set of models for a problem class from the candidates CONJURE produces, we use a set of training instances drawn from the target class. It is important that the training instances are discriminating. If all models solve a given instance in a trivial amount of time, or if no models solve it in the time available, then the instance is not useful for model selection. this paper addresses the task of generating small sets of discriminating training instances automatically. the instance space is determined by the parameters of the associated problem class. We develop a number of methods of finding parameter configurations that give discriminating training instances, some of them leveraging existing parameter-tuning techniques. Our experimental results confirm the success of our approach in reducing a large set of input models to a small set that we can expect to perform well for the given problem class.

关键词： Automation

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：