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

An efficient bounds consistency algorithm for the global cardinality constraint

constraintS 2005年第2期10卷 115-135页

作者： Quimper, CG Golynski, A López-Ortiz, A Van Beek, P Univ Waterloo Sch Comp Sci Waterloo ON N2L 3G1 Canada

Previous studies have demonstrated that designing special purpose constraint propagators can significantly improve the efficiency of a constraint programming approach. In this paper we present an efficient algorithm for bounds consistency propagation of the generalized cardinality constraint (gcc). Using a variety of benchmark and random problems, we show that on some problems our bounds consistency algorithm can dramatically outperform existing state-of-the-art commercial implementations of constraint propagators for the gcc. We also present a new algorithm for domain consistency propagation of the gcc which improves on the worst-case performance of the best previous algorithm for problems that occur often in applications.

关键词： global constraints bounds consistency domain consistency

来源：评论

学校读者我要写书评

暂无评论

Control abstractions for local search

引用

9th international conference on principles and practice of constraint programming

作者： Van Hentenryck, P Michel, L Brown Univ Providence RI 02912 USA Univ Connecticut Storrs CT 06269 USA

ISBN: (纸本)3540202021

COMET is an object-oriented language supporting a constraint-based architecture for local search through declarative and search components. this paper proposes three novel and lightweight control abstractions for the search component, significantly enhancing the compositionality, modularity, and reuse of COMET programs. these abstractions, which includes events and checkpoints, rely on first-class closures as the enabling technology. they are especially useful for expressing, in a modular way, heuristic and meta-heuristics, unions of heterogeneous neighborhoods, and sequential composition of neighborhoods.

关键词： incremental constraint local search neighborhood heuristic meta-heuristic control abstraction search

来源：评论

学校读者我要写书评

暂无评论

constraint programming for Mining n-ary Patterns

Constraint Programming for Mining n-ary Patterns

引用

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

作者： Khiari, Mehdi Boizumault, Patrice Cremilleux, Bruno Univ Caen Basse Normandie GREYC CNRS UMR 6072 F-14032 Caen France

ISBN: (纸本)9783642153952

the aim of this paper is to model and mine patterns combining several local patterns (n-ary patterns). First, the user expresses his/her query under constraints involving n-ary patterns. Second, a constraint solver generates the correct and complete set of solutions. this approach enables to model in a flexible way sets of constraints combining several local patterns and it leads to discover patterns of higher level. Experiments show the feasibility and the interest of our approach.

关键词： constraint theory

来源：评论

学校读者我要写书评

暂无评论

Control abstractions for local search

引用

constraintS 2005年第2期10卷 137-157页

作者： Van Hentenryck, P Michel, L Brown Univ Providence RI 02912 USA Univ Connecticut Storrs CT 06269 USA

关键词： incremental constraint local search neighborhood heuristic meta-heuristic control abstraction search

来源：评论

学校读者我要写书评

暂无评论

Maintaining longest paths incrementally

引用

constraintS 2005年第2期10卷 159-183页

作者： Katriel, I Michel, L Van Hentenryck, P Max Planck Inst Informat Saarbrucken Germany Univ Connecticut Storrs CT 06269 USA Brown Univ Providence RI 02912 USA

Modeling and programming tools for neighborhood search often support invariants, i.e., data structures specified declaratively and automatically maintained incrementally under changes. this paper considers invariants for longest paths in directed acyclic graphs, a fundamental abstraction for many applications. It presents bounded incremental algorithms for arc insertion and deletion which run in O ( ||delta|| + |delta| log |delta|) time and O ( ||delta||) time respectively, where |delta| and ||delta|| are measures of the change in the input and output. the paper also shows how to generalize the algorithm to various classes of multiple insertions/ deletions encountered in scheduling applications. Preliminary experimental results show that the algorithms behave well in practice.

关键词： incremental longest path heaviest path bounded computation graph constraint local search scheduling

来源：评论

学校读者我要写书评

暂无评论

Industrial Size Job Shop Scheduling Tackled by Present Day cp Solvers 25th

Industrial Size Job Shop Scheduling Tackled by Present Day C...

引用

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

作者： Da Col, Giacomo Teppan, Erich C. Alpen Adria Univ Klagenfurt A-9020 Klagenfurt Austria

ISBN: (纸本)9783030300487

the job shop scheduling problem (JSSP) is an abstraction of industrial scheduling and has been studied since the dawn of the computer era. Its combinatorial nature makes it easily expressible as a constraint satisfaction problem. Nevertheless, in the last decade, there has been a hiatus in the research on this topic from the constraint community;even when this problem is addressed, the target instances are from benchmarks that are more than 20 years old. And yet, constraint solvers have continued to evolve and the standards of today's industry have drastically changed. Our aim is to close this research gap by testing the capabilities of the best available cp solvers on the JSSP. We target not only the classic benchmarks from the literature but also a new benchmark of large-scale instances reflecting nowadays industrial scenarios. Furthermore, we analyze different encodings of the JSSP to measure the impact of high-level structures (such as interval variables and no-overlap constraints) on the problem solution. the solvers considered are OR-Tools, Google's open-source solver and winner of the last MiniZinc Challenge, and IBM's cp Optimizer, a proprietary solver targeted towards industrial scheduling problems.

关键词： constraint programming Job shop scheduling JSSP OR-Tools cp Optimizer Large-scale benchmark

来源：评论

学校读者我要写书评

暂无评论

Semi-automatic modeling by constraint acquisition

引用

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

作者： Coletta, Remi Bessière, Christian O’Sullivan, Barry Freuder, Eugene C. O’Connell, Sarah Quinqueton, Joel 161 rue Ada Montpellier Cedex 534392 France Cork Constraint Computation Centre Department of Computer Science University College Cork Ireland

ISBN: (纸本)3540202021

constraint programming is a technology which is now widely used to solve combinatorial problems in industrial applications. However, using it requires considerable knowledge and expertise in the field of constraint reasoning. this paper introduces a framework for automatically learning constraint networks from sets of instances that are either acceptable solutions or non-desirable assignments of the problem we would like to express. Such an approach has the potential to be of assistance to a novice who is trying to articulate her constraints. By restricting the language of constraints used to build the network, this could also assist an expert to develop an efficient model of a given problem. © Springer-Verlag Berlin Heidelberg 2003.

关键词： constraint programming

来源：评论

学校读者我要写书评

暂无评论

constraint symmetry for the soft CSP

Constraint symmetry for the soft CSP

引用

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

作者： Smith, Barbara M. Bistarelli, Stefano O'Sullivan, Barry Univ Leeds Sch Comp Leeds LS2 9JT W Yorkshire England CNR Ist Informat & Telemat I-00185 Pisa Italy Univ G dAnnunzio Dipartimento Sci Pescara Italy Univ Coll Cork Cork Constraint Computat Ctr Cork Ireland

ISBN: (纸本)9783540749691

We introduce a definition of constraint symmetry for soft CSPs, based on the definition of constraint symmetry for classical CSPs. We show that the constraint symmetry group of a soft CSP is a subgroup of that of an associated classical CSP instance. Where it is smaller, we can successfully exploit the additional symmetries using conditional symmetry breaking. We demonstrate, in a case-study of graph colouring, that eliminating the symmetry of the soft CSP combined with conditional symmetry breaking can lead to huge reductions in the search effort to find an optimal solution to the soft CSP.

关键词： constraint theory

来源：评论

学校读者我要写书评

暂无评论

Discrepancy-based additive bounding for the alldifferent constraint

引用

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

作者： Lodi, Andrea Milano, Michela Rousseau, Louis-Martin D.E.I.S Università di Bologna Viale Risorgimento 2 Bologna40136 Italy Centre for Research on Transportation Université de Montréal CP 6128 Succ Centre-Ville MontréalH3C 3J7 Canada

ISBN: (纸本)3540202021

In this paper we show how to exploit in constraint programming (cp) a well-known integer programming technique, the additive bounding procedure, when using Limited Discrepancy Search (LDS). LDS is an effective search strategy based on the concept of discrepancy, i.e., a branching decision which does not follow the suggestion of a given heuristic. the property of a node to have an associated discrepancy k can be modeled (and enforced) through a constraint, called k-discrepancy constraint. Our key result is the exploitation of the k-discrepancy constraint to improve the bound given by any relaxation of a combinatorial optimization problem by using the additive bounding idea. We believe that this simple idea can be effectively exploited to tighten relaxations in cp solvers and speed up the proof of optimality. the general use of additive bounding in conjunction with LDS has been presented in [14]. Here we focus on a particular case where the AllDifferent constraint is part of the cp model. In this case, the integration of additive bound in cp is particularly effective. © Springer-Verlag Berlin Heidelberg 2003.

关键词： constraint programming

来源：评论

学校读者我要写书评

暂无评论

Unifying Reserve Design Strategies with Graph theory and constraint programming 1

引用

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

作者： Justeau-Allaire, Dimitri Birnbaum, Philippe Lorca, Xavier CIRAD AMAP UMR F-34398 Montpellier France Inst Agron Neocaledonien IAC Noumea 98800 New Caledonia Univ Montpellier CIRAD AMAP CNRSINRAIRD Montpellier France IMT Mines Albi ORKID Ctr Genie Ind Campus Jarlard F-81013 Albi 09 France

ISBN: (数字)9783319983349

ISBN: (纸本)9783319983349;9783319983332

the delineation of areas of high ecological or biodiversity value is a priority of any conservation program. However, the selection of optimal areas to be preserved necessarily results from a compromise between the complexity of ecological processes and managers' constraints. Current reserve design models usually focus on few criteria, which often leads to an oversimplification of the underlying conservation issues. this paper shows that constraint programming (cp) can be the basis of a more unified, flexible and extensible framework. First, the reserve design problem is formalized. Secondly, the problem is modeled from two different angles by using two graph-based models. then cp is used to aggregate those models through a unique constraint Satisfaction Problem. Our model is finally evaluated on a real use case addressing the problem of rainforest fragmentation in New Caledonia, a biodiversity hotspot. Results are promising and highlight challenging perspectives to overtake in future work.

关键词： constraint satisfaction problems

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：