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

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

来源：评论

学校读者我要写书评

暂无评论

An MDD-based generalized arc consistency algorithm for positive and negative table constraints and some global constraints

引用

constraintS 2010年第2期15卷 265-304页

作者： Cheng, Kenil C. K. Yap, Roland H. C. Chinese Univ Hong Kong Dept Comp Sci & Engn Hong Kong Hong Kong Peoples R China Natl Univ Singapore Sch Comp Singapore 117548 Singapore

A table constraint is explicitly represented as its set of solutions or non-solutions. this ad hoc (or extensional) representation may require space exponential to the arity of the constraint, making enforcing GAC expensive. In this paper, we address the space and time inefficiencies simultaneously by presenting the mddc constraint. mddc is a global constraint that represents its (non-)solutions with a multi-valued decision diagram (MDD). the MDD-based representation has the advantage that it can be exponentially smaller than a table. the associated GAC algorithm (called mddc) has time complexity linear to the size of the MDD, and achieves full incrementality in constant time. In addition, we show how to convert a positive or negative table constraint into an mddc constraint in time linear to the size of the table. Our experiments on structured problems, car sequencing and still-life, show that mddc is also a fast GAC algorithm for some global constraints such as sequence and regular. We also show that mddc is faster than the state-of-the-art generic GAC algorithms in Gent et al. (2007), Lecoutre and Szymanek (2006), Lhomme and R,gin (2005) for table constraint.

关键词： Ad hoc constraint Global constraint Table constraint Positive constraint Negative constraint Multi-valued decision diagram Generalized arc consistency

来源：评论

学校读者我要写书评

暂无评论

An MDD-based generalized arc consistency algorithm for positive and negative table constraints and some global constraints

An MDD-based generalized arc consistency algorithm for posit...

引用

14th international conference on principles and practice of constraint programming (cp 2008)

作者： Cheng, Kenil C. K. Yap, Roland H. C. Chinese Univ Hong Kong Dept Comp Sci & Engn Hong Kong Hong Kong Peoples R China Natl Univ Singapore Sch Comp Singapore 117548 Singapore

关键词： Ad hoc constraint Global constraint Table constraint Positive constraint Negative constraint Multi-valued decision diagram Generalized arc consistency

来源：评论

学校读者我要写书评

暂无评论

New filtering algorithms for combinations of among constraints

引用

constraintS 2009年第2期14卷 273-292页

作者： van Hoeve, Willem-Jan Pesant, Gilles Rousseau, Louis-Martin Sabharwal, Ashish Ecole Polytech Montreal PQ H3C 3A7 Canada Carnegie Mellon Univ Tepper Sch Business Pittsburgh PA 15213 USA Univ Montreal CIRRELT Montreal PQ Canada Omega Optimisat Inc Montreal PQ Canada Cornell Univ Dept Comp Sci Ithaca NY 14853 USA

Several combinatorial problems, such as car sequencing and rostering, feature sequence constraints, restricting the number of occurrences of certain values in every subsequence of a given length. We present three new filtering algorithms for the sequence constraint, including the first that establishes domain consistency in polynomial time. the filtering algorithms have complementary strengths: One borrows ideas from dynamic programming;another reformulates it as a regular constraint;the last is customized. the last two algorithms establish domain consistency, and the customized one does so in polynomial time. We provide experimental results that demonstrate the practical usefulness of each. We also show that the customized algorithm applies naturally to a generalized version of the sequence constraint that allows subsequences of varied lengths. the significant computational advantage of using a single generalized sequence constraint over a semantically equivalent collection of among or sequence constraints is demonstrated empirically.

关键词： Sequence constraint Domain consistency Polynomial time filtering Car sequencing Regular constraint

来源：评论

学校读者我要写书评

暂无评论

Memoisation for constraint-based local search

Memoisation for constraint-based local search

引用

15th international conference on principles and practice of constraint programming, cp 2009

作者： Ågren, Magnus Swedish Institute of Computer Science Box 1263 Kista SE 164 29 Sweden

ISBN: (纸本)3642042430

We present a memoisation technique for constraint-based local search based on the observation that penalties with respect to some interchangeable elements need only be calculated once. We apply the technique to constraint-based local search on set variables, and demonstrate the usefulness of the approach by significantly speeding up the penalty calculation of a commonly used set constraint. © 2009 Springer Berlin Heidelberg.

关键词： Local search (optimization)

来源：评论

学校读者我要写书评

暂无评论

principles and practice of constraint programming - cp 2006 - 12th international conference, cp 2006, Proceedings

Principles and Practice of Constraint Programming - CP 2006 ...

引用

12th international conference on principles and practice of constraint programming, cp 2006

ISBN: (纸本)3540462678

the proceedings contain 61 papers. the topics discussed include: global optimization of probabilistically constrained linear programs;algorithms and constraint programming;infinite qualitative simulations by means of constraint programming;graph-properties based filtering;an algebraic characterization of complexity for valued constraints;typed guarded decompositions for constraint satisfaction;the minimum spanning tree constraint;performance prediction and automated tuning of randomized and parametric algorithms;adaptive clause weight redistribution;localization of an underwater robot using interval constraint propagation;approximability of integer programming with generalized constraints;generalized arc consistency for positive table constraints;and stochastic allocation and scheduling for conditional task graphs in MPSoCs.

关键词： constraint theory

来源：评论

学校读者我要写书评

暂无评论

MAX ONES generalized to larger domains

引用

SIAM JOURNAL ON COMPUTING 2008年第1期38卷 329-365页

作者： Jonsson, Peter Kuivinen, Fredrik Nordh, Gustav Linkoping Univ Dept Comp & Informat Sci SE-58183 Linkoping Sweden Ecole Polytech LIX F-91128 Palaiseau France

We study a family of problems, called Maximum Solution, where the objective is to maximize a linear goal function over the feasible integer assignments to a set of variables subject to a set of constraints. When the domain is Boolean (i.e., restricted to {0, 1}), the maximum solution problem is identical to the well-studied MAX ONES problem, and the approximability is completely understood for all restrictions on the underlying constraints [S. Khanna, M. Sudan, L. Trevisan, and D. P. Williamson, SIAM J. Comput., 30 (2001), pp. 1863-1920]. We continue this line of research by considering domains containing more than two elements. We present two main results: a complete classification for the approximability of all maximal constraint languages over domains of cardinality at most 4, and a complete classification of the approximability of the problem when the set of allowed constraints contains all permutation constraints. Under the assumption that a conjecture due to Szczepara [Minimal Clones Generated by Groupoids, Ph. D. thesis, Universite de Montreal, Montreal, QC, 1996] holds, we give a complete classification for all maximal constraint languages. these classes of languages are well studied in universal algebra and computer science;they have, for instance, been considered in connection with machine learning and constraint satisfaction. Our results are proved by using algebraic results from clone theory, and the results indicate that this approach is very powerful for classifying the approximability of certain optimization problems.

关键词： combinatorial optimization constraint satisfaction approximability universal algebra

来源：评论

学校读者我要写书评

暂无评论

Connecting ABT with Arc Consistency

引用

14th international conference on principles and practice of constraint programming (cp 2008)

作者： Brito, Ismel Meseguer, Pedro CSIC IIIA Bellaterra 09193 Spain

ISBN: (纸本)9783540859574

ABT is the reference algorithm for asynchronous distributed constraint satisfaction. When searching, ABT produces nogoods as justifications of deleted values. When one of such nogoods has an empty left-hand side, the considered value is eliminated unconditionally, once and for all. this value deletion can be propagated using standard arc consistency techniques, producing new deletions in the domains of other variables. this causes substantial reductions in the search effort required to solve a class of problems. We also extend this idea to the propagation of conditional deletions. something already proposed in the past. We provide experimental results that show the benefits of the proposed approach, especially considering communication cost.

关键词： constraint theory

来源：评论

学校读者我要写书评

暂无评论

GAC via unit propagation

GAC via unit propagation

引用

13th international conference on principles and practice of constraint programming (cp 2007)

作者： Bacchus, Fahiem Univ Toronto Dept Comp Sci Toronto ON Canada

ISBN: (纸本)9783540749691

In this paper we argue that an attractive and potentially very general way of achieving generalized are consistency (GAC) on a constraint is by using unit propagation (UP) over a CNF encoding of the constraint. this approach to GAC offers a number of advantages over traditional constraint specific algorithms (propagators): it is easier to implement, it automatically provides incrementality and decrementality in a backtracking context, and it can provide clausal reasons to support learning and non-chronological backtracking. Although UP on standard CNF encodings of a constraint fails to achieve GAC, we show here that alternate CNF encodings can be used on which UP does achieve GAC. We provide a generic encoding applicable to any constraint. We also give structure specific encodings for the regular, among, and gen-sequence constraints on which UP can achieve GAC with the same run time bounds as previously presented propagators. Finally, we explain how a UP engine can be added to a CSP solver to achieve a seamless integration of constraints encoded in CNF and propagated via UP and those propagated via traditional constraint specific propagators.

关键词： constraint theory

来源：评论

学校读者我要写书评

暂无评论

Failure analysis in backtrack search for constraint satisfaction

Failure analysis in backtrack search for constraint satisfac...

引用

12th international conference on principles and practice of constraint programming (cp 2006)

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：