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

Solution counting algorithms for constraint-centered search heuristics

constraintS 2009年第3期14卷 392-413页

作者： Zanarini, Alessandro Pesant, Gilles Ecole Polytech Dept Comp & Software Engn Montreal PQ H3C 3A7 Canada

constraints have played a central role in cp because they capture key substructures of a problem and efficiently exploit them to boost inference. this paper intends to do the same thing for search, proposing constraint-centered heuristics which guide the exploration of the search space toward areas that are likely to contain a high number of solutions. We first propose new search heuristics based on solution counting information at the level of individual constraints. We then describe efficient algorithms to evaluate the number of solutions of two important families of constraints: occurrence counting constraints, such as all different, and sequencing constraints, such as regular. In both cases we take advantage of existing filtering algorithms to speed up the evaluation. Experimental results on benchmark problems show the effectiveness of our approach.

关键词： Solution counting Heuristic search Regular constraint Alldifferent constraint

来源：评论

学校读者我要写书评

暂无评论

constraints of Difference and Equality: A Complete Taxonomic Characterisation

Constraints of Difference and Equality: A Complete Taxonomic...

引用

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

作者： Hebrard, Emmanuel Marx, Daniel O'Sullivan, Barry Razgon, Igor Natl Univ Ireland Univ Coll Cork Cork Constraint Computat Ctr Dept Comp Sci Cork Ireland Budapest Univ Technol & Econ Budapest Hungary

ISBN: (纸本)9783642042430

Many combinatorial problems encountered in practice involve constraints that require that a, set of variables take distinct or equal values. the ALLDIFFERENT constraint, in particular, ensures that;all variables take distinct values. Two soft variants of this constraint were proposed ill [4];defined either with respect to a so-called variable or graph-based cost function. When requiring similarity, as' opposed to diversity, one can consider the dual definition either for the cost;or for the basic constraint, itself, that is, ALLEQUAL in our case. Six cost, functions call be defined by exploring every combination of these definitions. It is therefore natural to study the complexity of achieving arc consistency and bounds consistency oil them. From our earlier work oil this topic all open problem remained, namely achieving bounds Consistency oil the maximisation of the SOFTALLDIFF constraint when considering the graph-based cost. In this paper we resolve this problem. therefore. we give a complete taxonomy of constraints of equality and difference, based oil the alternative objective functions used for the soft, variants.

关键词： Cost functions

来源：评论

学校读者我要写书评

暂无评论

the Complexity of Valued constraint Models

The Complexity of Valued Constraint Models

引用

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

作者： Zivny, Stanislav Jeavons, Peter G. Univ Oxford Comp Lab Oxford OX1 3QD England

ISBN: (纸本)9783642042430

the VALUED constraint SATISFACTION PROBLEM (VCSP) is a general framework encompassing many optimisation problems. We discuss precisely what;it means for a, problem to be modelled in the VCSP framework. Using our analysis, we show that some optimisation problems, such as (s,t)-MIN-CUT and SUBMODULAR FUNCTION MINIMISATION, can be modelled using a restricted Set Of valued constraints which axe tractable to solve regard less of how they are combined. Hence, these problems can be viewed as special cases of more general problems which include all possible instances rising the same forms., of valued constraint. However, other, apparently similar, problems such as MINCUT and SYMMETRIC SUBMODULAR FUNCTION MINIMISATION, which also have polynomial-time algorithms, can only be naturally modelled in the VCSP framework by using valued constraints which can represent NP-complete problems. this suggests that the reason for tractability ill these problems is more subtle: it relies not;Only Oil the form of the valued constraints, but;also on the precise structure of the problem. Furthermore, our results suggest that allowing constant constraints can significantly alter the complexity of problems in the VScp framework, in contrast, to the CSP framework.

关键词： Computational complexity

来源：评论

学校读者我要写书评

暂无评论

Minimising Decision Tree Size as Combinatorial Optimisation

Minimising Decision Tree Size as Combinatorial Optimisation

引用

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

作者： Bessiere, Christian Hebrard, Emmanuel O'Sullivan, Barry LIRMM Montpellier France Univ Coll Cork Cork Constraint Computat Ctr Dept Comp Sci Cork Ireland

ISBN: (纸本)9783642042430

Decision tree induction techniques attempt to find small trees that fit a training set of data. this preference for smaller trees, which provides a learning bias, is often justified its being consistent with the principle of Occam's Razor. Informally, this principle states that One Should prefer the simpler hypothesis. In this paper we take this principle to the extreme. Specifically, we formulate decision tree induction its it combinatorial optimisation problem in which the objective is to minimise the number of nodes in the tree. We study alternative formulations based on satisfiability, constraint programming, and hybrids with integer linear programming. We empirically compare Our approaches against standard induction algorithms, showing that the decision trees we obtain can sometimes be less than half the size of those found by other greedy methods. Furthermore, our decision trees are competitive in terms of accuracy on a variety of well-known benchmarks, often being the most accurate. Even when post-pruning of greedy trees is used, Our constraint-based approach is never dominated by any of the existing techniques.

关键词： Decision trees

来源：评论

学校读者我要写书评

暂无评论

Confidence-Based Work Stealing in Parallel constraint programming

Confidence-Based Work Stealing in Parallel Constraint Progra...

引用

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

作者： Chu, Geoffrey Schulte, Christian Stuckey, Peter J. Univ Melbourne Victoria Lab Dept Comp Sci & Software Engn Natl ICT Australia Melbourne Vic 3010 Australia KTH Royal Inst Technol Stockholm Sweden

ISBN: (纸本)9783642042430

the most popular architecture for parallel search is work stealing: threads that have run out of work (nodes to be searched) steal from threads that still have work. Work stealing not only allows for dynamic load balancing, but also determines which parts of the search tree are searched next. thus the place from where work is stolen has a dramatic effect oil the efficiency of a parallel search algorithm. this paper examines quantitatively low optimal work stealing call be performed given an estimate of the relative solution densities of the subtrees at each search tree node and relates it to the branching heuristic strength. An adaptive work stealing algorithm is presented that automatically performs different work stealing strategies based oil the confidence of the branching heuristic at each node. Many parallel depth-first search patterns arise naturally from this algorithm. the algorithm produces near perfect or super linear algorithmic efficiencies oil all problems tested. Real speedups using 8 threads range from 7 times to super linear.

关键词： Efficiency

来源：评论

学校读者我要写书评

暂无评论

constraint-Based Optimal Testing Using DNNF Graphs

Constraint-Based Optimal Testing Using DNNF Graphs

引用

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

作者： Schumann, Anika Sachenbacher, Martin Huang, Jinbo Univ Coll Cork Cork Constraint Computat Ctr Cork Ireland Australian Natl Univ Canberra ACT 0200 Australia NICTA Sydney NSW Australia Tech Univ Munich Inst Informat Munich Germany

ISBN: (纸本)9783642042430

the goal of testing is to distinguish between a number of hypotheses about a system-for example, different diagnoses of faults-by applying input patterns and verifying or falsifying the hypotheses from the observed outputs. Optimal distinguishing tests (ODTs) are those input patterns that are most likely to distinguish between hypotheses about, non-deterministic systems. Finding ODTs is practically important, but it;amounts in general to determining a ratio of model counts and is therefore computationally very expensive. In this paper, we present a novel approach to constraint-based ODT generation, which uses structural properties of the system to limit the complexity of computation. We first construct. a compact graphical representation of the testing problem via compilation into decomposable negation normal form. Based on this compiled representation, we show how one can evaluate distinguishing tests in linear time, which allows us to efficiently determine an ODT. Experimental results from a real-world application show that our method can compute ODTs for instances that were intractable for previous approaches.

关键词： Algorithms applications testing DNNF graphs

来源：评论

学校读者我要写书评

暂无评论

Search Space Extraction

Search Space Extraction

引用

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

作者： Mehta, Deepak O'Sullivan, Barry Quesada, Luis Wilson, Nic Natl Univ Ireland Univ Coll Cork Cork Constraint Computat Ctr Dept Comp Sci Cork Ireland

ISBN: (纸本)9783642042430

Systematic tree search is often used in Conjunction with inference and restarts when solving challenging constraint Satisfaction Problems (CSPs). In order to improve the efficiency of constraint solving, techniques that learn during search, such as constraint weighting and nogood learning. have been proposed. constraint weights can be used to guide heuristic choices. Nogood assignments can be avoided by adding additional constraints. Both of these techniques can be used in either one-shot systematic search, or in a setting in which we frequently restart the search procedure. In this paper we propose a third way of learning during search, generalising previous work by Freuder and Hubbe. Specifically, we show how, in a restart context, we can guarantee that we avoid revisiting a previously visited region of the search space by extracting it from the problem. Likewise, we can avoid revisiting inconsistent regions of the search space by extracting inconsistent subproblems, based on a significant improvement upon Freuder and Hubbe's approach. A major empirical result of this paper is that our approach significantly outperforms MAC combined with weighted degree heuristics and restarts on challenging constraint problems. Our approach can be regarded as an efficient form of learning that does not rely on constraint propagation. Instead, we rely on a reformulation of a CSP into an equivalent set of CSPs, none of which contain any of the search space we wish to avoid.

关键词： constraint satisfaction problems

来源：评论

学校读者我要写书评

暂无评论

constraint programming Applied to the Multi-Skill Project Scheduling Problem 23rd

Constraint Programming Applied to the Multi-Skill Project Sc...

引用

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)

作者： Young, Kenneth D. Feydy, thibaut Schutt, Andreas Univ Melbourne Melbourne Vic Australia CSIRO Decis Sci Data61 Melbourne Vic Australia

ISBN: (纸本)9783319661582;9783319661575

the Multi-Skill Project Scheduling Problem is a variant of the well-studied Resource Constrained Project Scheduling Problem, in which the resources are assumed to be multi-skilled. Practical applications of this problem occur when the resources considered are a multi-skilled workforce or multi-purpose machines. this variant introduces a set of assignment decisions between the resources and activities, further to the usual scheduling decisions. this additional layer of complexity results in the problem becoming far more difficult to solve. We investigate different constraint programming models and searches tailored for solvers with nogood learning. these models and searches are then evaluated on instances available from the literature as well as newly generated ones. Using the best performing model and search, we are able to close at least 87 open instances from the literature.

关键词： constraint programming

来源：评论

学校读者我要写书评

暂无评论

the proper treatment of undefinedness in constraint languages

The proper treatment of undefinedness in constraint language...

引用

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

作者： Frisch, Alan M. Stuckey, Peter J. Artificial Intelligence Group Dept. of Computer Science Univ. of York United Kingdom National ICT Australia Dept. of Computer Science and Software Engineering Univ. of Melbourne Australia

ISBN: (纸本)3642042430

Any sufficiently complex finite-domain constraint modelling language has the ability to express undefined values, for example division by zero, or array index out of bounds. this paper gives the first systematic treatment of undefinedness for finite-domain constraint languages. We present three alternative semantics for undefinedness, and for each of the semantics show how to map models that contain undefined expressions into equivalent models that do not. the resulting models can be implemented using existing constraint solving technology. © 2009 Springer Berlin Heidelberg.

关键词： Modeling languages

来源：评论

学校读者我要写书评

暂无评论

constraint Representations and Structural Tractability

Constraint Representations and Structural Tractability

引用

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

作者： Cohen, David A. Green, Martin J. Houghton, Chris Univ London Dept Comp Sci London WC1E 7HU England

ISBN: (纸本)9783642042430

the intractability of the general CSP has motivated the search for restrictions which lead to tractable fragments. One way to achieve tractability is to restrict;Hie structure of the instances. As much of the, work in this area arises from similar work oil databases it has been a natural assumption Oat all constraint relations are explicitly represented. If this is the case then all instances with an acyclic hypergraph structure are tractable. Unfortunately this result does not hold if we are allowed to represent constraint relations implicitly: the class of SAT instances with acyclic hypergraph structure is NP-hard. Continuing the work of Chen and Grohe on the succinct GDNF representation we develop the theory of structural tractability for an extension to the table constraint that has a succinct representation of SAT clauses. this mixed representation is less succinct than the GDNF representation but more succinct than the table representation. We prove a strict hierarchy of structural tractability for the GDNF. the mixed, and the explicit representations of constraint relations. Using this proof we are able to show that the mixed representation provides novel tractable structural classes. Since the mixed representation naturally extends SAT, this provides a useful result, extending known structural tractability results for SAT. Under. a, natural restriction we are able precisely to capture the tractable structure classes for this mixed representation. this gives us an extension of Grohe's dichotomy theorem for the tractability of classes of relational structures with a. fixed signature, hi particular it captures, the tractability of some classes of unbounded arity, specifically the class of CSPs with precisely one constraint.

关键词： constraint satisfaction problems

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：