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

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

作者： Deville, Yves Van Hentenryck, Pascal Catholic Univ Louvain Louvain Belgium Brown Univ Providence RI 02912 USA

ISBN: (纸本)9783642153952

this paper presents a novel domain-consistency algorithm which does not maintain supports dynamically during propagation, but rather maintain forbidden values. It introduces the optimal NAC4 (negative AC4) algorithm based on this idea. It further shows that maintaining forbidden values dynamically allows the generic algorithm AC5 to achieve domain consistency in time O(ed) for classes of constraints in which the number of supports is O(d(2)) but the number of forbidden values is O(d). the paper also shows how forbidden values and supports can be used jointly to achieve domain consistency on logical combinations of constraints and to compute validity as well as entailment of constraints. Experimental results show the benefits of the joint exploitation of supports and forbidden values.

关键词： Computer programming

来源：评论

学校读者我要写书评

暂无评论

On Testing constraint Programs

On Testing Constraint Programs

引用

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

作者： Lazaar, Nadjib Gotlieb, Arnaud Lebbah, Yahia INRIA Rennes Bretagne Atlantique Campus Beaulieu F-35042 Rennes France Univ Oran Es Senia LITIO Orange NSW Australia Univ Nice Sophia Antipolis Antipolis France

ISBN: (纸本)9783642153952

the success of several constraint-based modeling languages such as OPL, ZINC, or COMET, appeals for better software engineering practices, particularly in the testing phase. this paper introduces a testing framework enabling automated test case generation for constraint programming. We propose a general framework of constraint program development which supposes that a first declarative and simple constraint model is available from the problem specifications analysis. then, this model is refined using classical techniques such as constraint reformulation, surrogate and global constraint addition, or symmetry-breaking to form an improved constraint model that must be thoroughly tested before being used to address real-sized problems. We think that most of the faults are introduced in this refinement step and propose a process which takes the first declarative model as an oracle for detecting non-conformities. We derive practical test purposes from this process to generate automatically test data that exhibit non-conformities. We implemented this approach in a new tool called CPTEST that was used to automatically detect non-conformities on two classical benchmark programs, namely the Golomb rulers and the car-sequencing problem.

关键词： Modeling languages

来源：评论

学校读者我要写书评

暂无评论

SMT-Based constraint Answer Set Solver EZSMT⁺ for Non-Tight Programs 16

SMT-Based Constraint Answer Set Solver EZSMT<SUP>+</SUP> for...

引用

16th international conference on principles of Knowledge Representation and Reasoning

作者： Shen, Da Lierler, Yuliya Univ Nebraska Dept Comp Sci Omaha NE 68182 USA

ISBN: (纸本)9781577358039

constraint answer set programming integrates answer set programming with constraint processing. System EZSMT(+) is a constraint answer set programming tool that utilizes satisfiability modulo theory solvers for search. the truly unique feature of EZSMT(+) is its capability to process linear as well as nonlinear constraints simultaneously containing integer and real variables.

关键词： Real variables

来源：评论

学校读者我要写书评

暂无评论

A Complete Multi-valued SAT Solver

A Complete Multi-valued SAT Solver

引用

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

作者： Jain, Siddhartha O'Mahony, Eoin Sellmann, Meinolf Brown Univ Dept Comp Sci POB 1910 Providence RI 02912 USA Univ Coll Cork Cork Constraint Comp Ctr Cork Ireland

ISBN: (纸本)9783642153952

We present a new complete multi-valued SAT solver, based on current state-of-the-art SAT technology. It features watched literal propagation and conflict driven clause learning. We combine this technology with state-of-the-art CP methods for branching and introduce quantitative supports which augment the watched literal scheme with a watched domain size scheme. Most importantly, we adapt SAT nogood learning for the multi-valued case and demonstrate that exploiting the knowledge that each variable must take exactly one out of many values can lead to much stronger nogoods. Experimental results assess the benefits of these contributions and show that solving multi-valued SAT directly often works better than reducing multi-valued constraint problems to SAT.

关键词： Model checking

来源：评论

学校读者我要写书评

暂无评论

Using Learnt Clauses in MAXSAT

Using Learnt Clauses in MAXSAT

引用

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

作者： Davies, Jessica Cho, Jeremy Bacchus, Fahiem Univ Toronto Dept Comp Sci Toronto ON M5S 1A1 Canada

ISBN: (纸本)9783642153952

MAXSAT is an optimization version of SAT capable of expressing a variety of practical problems. MAXSAT solvers have been designed to take advantage of many of the successful techniques of SAT solvers. However, the most important technique of modern SAT solvers, clause learning, has not been utilized since learnt clauses cannot be soundly added to a MAXSAT theory. In this paper we present a new method that allows SAT clause learning to be exploited in a MAXSAT solver without losing soundness. We present techniques for learning clauses during a branch and bound (B&B) MAXSAT search, a process that is more complicated than standard clause learning. To exploit these learnt clauses we develop a connection between them and bounds that can be used during B&B. this connection involves formulating a hitting set problem and finding bounds on its optimal solution. We present some new techniques for generating useful hitting set bounds and also show how linear and integer programs can be exploited for this purpose, opening the door for a hybrid approach to solving MAXSAT.

关键词： Integer programming

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Applying constraint programming to Identification and Assignment of Service Professionals

Applying Constraint Programming to Identification and Assign...

引用

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

作者： Asaf, Sigal Eran, Haggai Richter, Yossi Connors, Daniel P. Gresh, Donna L. Ortega, Julio Mcinnis, Michael J. Univ Haifa Campus IBM Haifa Res Lab IL-31905 Haifa Israel Thomas J Watson Res Ctr IBM Res Div Yorktown Hts NY USA IBM Global Business Serv Dallas TX 1503 USA IBM Global Business Serv Southbury CT 06488 USA

ISBN: (纸本)9783642153952

Today many companies face the challenge of matching highly-skilled professionals to high-end positions in large organizations and human deployment agencies. Non-accurate matches in these businesses can result in significant monetary losses and other negative effects. Unlike traditional Workforce Management (WM) problems such as shift scheduling, highly-skilled employees are professionally distinguishable from each other and hence non-interchangeable. therefore, the techniques used for shift-scheduling can't be applied to the highly-skilled WM domain. Our work focuses on providing a constraint programming solution for supporting the assignment of highly-skilled professionals. Our experience shows that CP is well adapted to this problem. CP supports very well the underlying constraints. In addition, the rich expressive language supported by CP allows us to provide a convenient mechanism for changing and adding new matching and preference constraints. Based on this technology, we have built a tool that is currently being used by IBM service organizations and provides strong business results.

关键词： Human resource management

来源：评论

学校读者我要写书评

暂无评论

Two contributions of constraint programming to machine learning

引用

16th European conference on Machine Learning (ECML)/9th European conference on principles and practice of Knowledge Discovery in Databases (PKDD)

作者： Lallouet, A Legtchenko, A Univ Orleans LIFO F-45067 Orleans France

ISBN: (纸本)3540292438

A constraint is a relation with an active behavior. For a given relation, we propose to learn a representation adapted to this active behavior. It yields two contributions. the first is a generic metatechnique for classifier improvement showing performances comparable to boosting. the second lies in the ability of using the learned concept in constraint-based decision or optimization problems. It opens a new way of integrating Machine Learning in Decision Support Systems.

关键词： Learning systems

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：