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

constraint models for the covering test problem

constraintS 2006年第2-3期11卷 199-219页

作者： Hnich, Brahim Prestwich, Steven D. Selensky, Evgeny Smith, Barbara M. Izmir Univ Econ Fac Comp Sci Izmir Turkey Natl Univ Ireland Univ Coll Cork Cork Constraint Computat Ctr Cork Ireland Vidus Ltd Ipswich Suffolk England

Covering arrays can be applied to the testing of software, hardware and advanced materials, and to the effects of hormone interaction on gene expression. In this paper we develop constraint programming models of the problem of finding an optimal covering array. Our models exploit global constraints, multiple viewpoints and symmetry-breaking constraints. We show that compound variables, representing tuples of variables in our original model, allow the constraints of this problem to be represented more easily and hence propagate better. With our best integrated model, we are able to either prove the optimality of existing bounds or find new optimal solutions, for arrays of moderate size. Local search on a SAT-encoding of the model is able to find improved solutions and bounds for larger problems.

关键词： modelling covering arrays symmetry local search testing chanelling constraints global constraints

来源：评论

学校读者我要写书评

暂无评论

the ROOTS constraint

The ROOTS constraint

引用

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

作者： Bessiere, Christian Hebrard, Emmanuel Hnich, Brahim Kiziltan, Zeynep Walsh, Toby Univ Montpellier CNRS LIRMM F-34059 Montpellier France 4C Cork Ireland Natl Univ Ireland Univ Coll Cork Cork Ireland Izmir Univ Econ Izmir Turkey Univ Bologna Bologna Italy NICTA Sydney NSW Australia UNSW Sydney NSW Australia

ISBN: (纸本)3540462678

A wide range of counting and occurrence constraints can be specified with just two global primitives: the RANGE constraint, which computes the range of values used by a sequence of variables, and the ROOTS constraint, which computes the variables mapping onto a set of values. We focus here on the ROOTS constraint. We show that propagating the ROOTS constraint completely is intractable. We therefore propose a decomposition which can be used to propagate the constraint in linear time. Interestingly, for all uses of the ROOTS constraint we have met, this decomposition does not destroy the global nature of the constraint as we still prune all possible values. In addition, even when the ROOTS constraint is intractable to propagate completely, we can enforce bound consistency in linear time simply by enforcing bound consistency on the decomposition. Finally, we show that specifying counting and occurrence constraints using ROOTS is effective and efficient in practice on two benchmark problems from CSPLib.

关键词： constraint theory

来源：评论

学校读者我要写书评

暂无评论

Mini-bucket elimination with bucket propagation

Mini-bucket elimination with bucket propagation

引用

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

作者： Rollon, Emma Larrosa, Javier Univ Politecn Cataluna Barcelona 08034 Spain

ISBN: (纸本)3540462678

Many important combinatorial optimization problems can be expressed as constraint satisfaction problems with soft constraints. When problems are too difficult to be solved exactly, approximation methods become the best option. Mini-bucket Elimination (MBE) is a well known approximation method for combinatorial optimization problems. It has a control parameter z that allow us to trade time and space for accuracy. In practice, it is the space and not the time that limits the execution with high values of z. In this paper we introduce a new propagation phase that MBE should execute at each bucket. the purpose of this propagation is to jointly process as much information as possible. As a consequence, the undesirable lose of accuracy caused by MBE when splitting functions into different mini-buckets is minimized. We demonstrate our approach in scheduling, combinatorial auction and max-clique problems, where the resulting algorithm MBEP gives important percentage increments of the lower bound (typically 50% and up to 1566%) with only doubling the cpu time.

关键词： constraint theory

来源：评论

学校读者我要写书评

暂无评论

constraint satisfaction with bounded treewidth revisited

Constraint satisfaction with bounded treewidth revisited

引用

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

作者： Samer, Marko Szeider, Stefan Vienna Univ Technol Inst Informat Syst DBAI Vienna Austria Univ Durham Dept Comp Sci Durham DH1 3HP England

ISBN: (纸本)3540462678

the constraint satisfaction problem can be solved in polynomial time for instances where certain parameters (e.g., the treewidth of primal graphs) are bounded. However, there is a trade-off between generality and performance: larger bounds on the parameters yield worse time complexities. It is desirable to pay for more generality only by a constant factor in the running time, not by a larger degree of the polynomial. Algorithms with such a uniform polynomial time complexity are known as fixed-parameter algorithms. In this paper we determine whether or not fixed-parameter algorithms for constraint satisfaction exist, considering all possible combinations of the following parameters: the treewidth of primal graphs, the treewidth of dual graphs, the treewidth of incidence graphs, the domain size, the maximum arity of constraints, and the maximum size of overlaps of constraint scopes. the negative cases are subject to the complexity theoretic assumption FPT not equal W[1] which is the parameterized analog to P not equal NP. For the positive cases we provide an effective fixed-parameter algorithm which is based on dynamic programming on "nice" tree decompositions.

关键词： constraint theory

来源：评论

学校读者我要写书评

暂无评论

CoJava: Optimization modeling by nondeterministic simulation

CoJava: Optimization modeling by nondeterministic simulation

引用

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

作者： Brodsky, Alexander Nash, Hadon George Mason Univ Fairfax VA 22030 USA

ISBN: (纸本)3540462678

We have proposed and implemented the language CoJava, which offers both the advantages of simulation-like process modeling in Java, and the capabilities of true decision optimization. By design, the syntax of CoJava is identical to the programming language Java, extended with special constructs to (1) make a nondeterministic choice of a numeric value, (2) assert a constraint, and (3) designate a program variable as the objective to be optimized. A sequence of specific selections in nondeterministic choice statements corresponds to an execution path. We define an optimal execution path as one that (1) satisfies the range conditions in the choice statements, (2) satisfies the assert-constraint statements, and (3) produces the optimal value in a designated program variable, among all execution paths that satisfy (1) and (2). the semantics of a CoJava program amounts to first finding an optimal execution path, and then procedurally executing it. To find an optimal execution path, the implemented CoJava compiler reduces the problem to a standard optimization formulation, and then solves it on an external solver. then, the CoJava program is run as a Java program, where the choice statements select the found optimal values, and the assert and optimization statements are ignored. We illustrate the usage and semantics of CoJava using a simple supply-chain example, in which elastic demand, a manufacturer and a supplier are modeled as Java classes.

关键词： Java programming language

来源：评论

学校读者我要写书评

暂无评论

Generalized Arc Consistency for positive table constraints

Generalized Arc Consistency for positive table constraints

引用

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

作者： Lecoutre, Christophe Szymanek, Radoslaw Univ Artois CRIL CNRS FRE 2499 Lens France Natl Univ Ireland Univ Coll Cork Cork Constraint Computat Ctr Cork Ireland

ISBN: (纸本)3540462678

In this paper, we propose a new algorithm to establish Generalized Arc Consistency (GAC) on positive table constraints, i.e. constraints defined in extension by a set of allowed tuples. Our algorithm visits the lists of valid and allowed tuples in an alternative fashion when looking for a support (i.e. a tuple that is both allowed and valid). It is then able to jump over sequences of valid tuples containing no allowed tuple and over sequences of allowed tuples containing no valid tuple. Our approach, that can be easily grafted to any generic GAC algorithm, admits on some instances a behaviour quadratic in the arity of the constraints whereas classical approaches, i.e. approaches that focus on either valid or allowed tuples, admit an exponential behaviour. We show the effectiveness of this approach, both theoretically and experimentally.

关键词： constraint theory

来源：评论

学校读者我要写书评

暂无评论

Dynamic ordering for asynchronous backtracking on DisCSPs

引用

constraintS 2006年第2-3期11卷 179-197页

作者： Zivan, Roie Meisels, Amnon Ben Gurion Univ Negev Dept Comp Sci IL-84105 Beer Sheva Israel

An algorithm that performs asynchronous backtracking on distributed CSPs, with dynamic ordering of agents is proposed, ABT_DO. Agents propose reorderings of lower priority agents and send these proposals whenever they send assignment messages. Changes of ordering triggers a different computation of Nogoods. the dynamic ordered asynchronous backtracking algorithm uses polynomial space, similarly to standard ABT. the ABT_DO algorithm with three different ordering heuristics is compared to standard ABT on randomly generated DisCSPs. A Nogood-triggered heuristic, inspired by dynamic backtracking, is found to outperform static order ABT by a large factor in run-time and improve the network load.

关键词： distributed constraint satisfaction distributed AI search

来源：评论

学校读者我要写书评

暂无评论

Symmetry definitions for constraint satisfaction problems

引用

constraintS 2006年第2-3期11卷 115-137页

作者： Cohen, David Jeavons, Peter Jefferson, Christopher Petrie, Karen E. Smith, Barbara M. Natl Univ Ireland Univ Coll Cork Cork Constraint Computat Ctr Cork Ireland Univ London Royal Holloway Dept Comp Sci London England Univ Oxford Comp Lab Oxford OX1 3QD England Univ St Andrews Sch Comp Sci St Andrews KY16 9AJ Fife Scotland

We review the many different definitions of symmetry for constraint satisfaction problems (CSPs) that have appeared in the literature, and show that a symmetry can be defined in two fundamentally different ways: as an operation preserving the solutions of a CSP instance, or else as an operation preserving the constraints. We refer to these as solution symmetries and constraint symmetries. We define a constraint symmetry more precisely as an automorphism of a hypergraph associated with a CSP instance, the microstructure complement. We show that the solution symmetries of a CSP instance can also be obtained as the automorphisms of a related hypergraph, the k-ary nogood hypergraph and give examples to show that some instances have many more solution symmetries than constraint symmetries. Finally, we discuss the practical implications of these different notions of symmetry.

关键词： constraint satisfaction problems symmetry

来源：评论

学校读者我要写书评

暂无评论

Retroactive ordering for dynamic backtracking

Retroactive ordering for dynamic backtracking

引用

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

作者： Zivan, Roie Shapen, Uri Zazone, Moshe Meisels, Amnon Ben Gurion Univ Negev Dept Comp Sci IL-84105 Beer Sheva Israel

ISBN: (纸本)3540462678

Dynamic Backtracking (DBT) is a well known algorithm for solving constraint Satisfaction Problems. In DBT, variables are allowed to keep their assignment during backjump, if they are compatible with the set of eliminating explanations. A previous study has shown that when DBT is combined with variable ordering heuristics it performs poorly compared to standard Conflict-directed Backjumping (CBJ) [1]. the special feature of DBT, keeping valid elimination explanations during backtracking, can be used for generating a new class of ordering heuristics. In the proposed algorithm, the order of already assigned variables can be changed. Consequently, the new class of algorithms is termed Retroactive DBT. In the proposed algorithm, the newly assigned variable can be moved to a position in front of assigned variables with larger domains and as a result prune the search space more effectively. the experimental results presented in this paper show an advantage of the new class of heuristics and algorithms over standard DBT and over CBJ. All algorithms tested were combined with forward-checking and used a Min-Domain heuristic.

关键词： constraint theory

来源：评论

学校读者我要写书评

暂无评论

Distributed constraint-based local search

Distributed constraint-based local search

引用

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

作者： Michel, Laurent See, Andrew Van Hentenryck, Pascal Univ Connecticut Storrs CT 06269 USA Brown Univ Providence RI 02912 USA

ISBN: (纸本)3540462678

Distributed computing is increasingly important at a time when the doubling of the number of transistors on a processor every 18 months no longer translates in a doubling of speed but instead a doubling of the number of cores. Unfortunately, it also places significant conceptual and implementation burden on programmers. this paper aims at addressing this challenge for constraint-based local search (CBLS), whose search procedures typically exhibit inherent parallelism stemming from multistart, restart, or population-based techniques whose benefits have been demonstrated both experimentally and theoretically. the,paper presents abstractions that allows distributed CBLS programs to be close to their sequential and parallel counterparts, keeping the conceptual and implementation overhead of distributed computing minimal. A preliminary implementation in COMET exhibits significant speed-ups in constraint satisfaction and optimization applications. the implementation also scales well with the number of machines. Of particular interest is the observation that generic abstractions of CBLS and CP, such as models and solutions, and advanced control structures such as events and closures, play a fundamental role to keep the distance between sequential and distributed CBLS programs small. As a result, the abstractions directly apply to CP programs using multistarts or restarts procedures.

关键词： constraint theory

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：