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

Strong cost-based filtering for Lagrange decomposition applied to network design

10th international conference on the principles and practice of constraint programming

作者： Cronholm, W Ajili, F Univ London Imperial Coll Sci Technol & Med London SW7 2AZ England

ISBN: (纸本)3540232419

this paper describes a new hybrid algorithm for a multicast network design application. the problem consists of finding a minimum-cost topology and link dimensions subject to capacity and multicast routing constraints. the algorithm exploits Lagrange Decomposition (LD) to yield separable subproblems. Each subproblem has a constraint programming relaxation. We derive a sharper cost bound and stronger cost-based filtering rules. the results indicate that our solver outperforms the pure LD approach.

关键词： Multicasting

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Towards Practical Infinite Stream constraint programming: Applications and Implementation

Towards Practical Infinite Stream Constraint Programming: Ap...

引用

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

作者： Lee, Jasper C. H. Lee, Jimmy H. M. Univ Cambridge Churchill Coll Cambridge CB2 1TN England Chinese Univ Hong Kong Dept Comp Engn & Sci Sha Tin Peoples R China

ISBN: (纸本)9783319104287;9783319104270

Siu et al. propose stream CSPs (St-CSPs) as a generalisation of finite domain CSPs to cater for constraints on infinite streams, and a solving algorithm that produces a deterministic Buchi automaton recognising the solution language. As a novel application, we demonstrate how St-CSPs can model mathematically and generate a PID controller for driving a self-balancing tray and an inverted pendulum in real-time. We propose and give formally the correctness of an improvement to the implementation that eliminates numerous unnecessary states in the solution automaton for St-CSPs involving the first temporal operator, thereby reducing solving time. We give two St-CSP examples that can benefit from our new implementation techniques. Our approach always generates a solution automaton not bigger than, but potentially exponentially smaller than, that produced by the original implementation. Experimental results show substantial improvements.

关键词： Inverted pendulum

来源：评论

学校读者我要写书评

暂无评论

Fast Matrix Multiplication Without Tears: A constraint programming Approach 29

Fast Matrix Multiplication Without Tears: A Constraint Progr...

引用

29th international conference on principles and practice of constraint programming, cp 2023

作者： Deza, Arnaud Liu, Chang Vaezipoor, Pashootan Khalil, Elias B. Department of Mechanical and Industrial Engineering University of Toronto Canada Department of Computer Science University of Toronto Canada

ISBN: (纸本)9783959773003

It is known that the multiplication of an N ×M matrix with an M ×P matrix can be performed using fewer multiplications than what the naive NMP approach suggests. the most famous instance of this is Strassen's algorithm for multiplying 2 × 2 matrices in 7 instead of 8 multiplications. this gives rise to the constraint satisfaction problem of fast matrix multiplication, where a set of R © Arnaud Deza, Chang Liu, Pashootan Vaezipoor, and Elias B. Khalil.

关键词： constraint satisfaction problems

来源：评论

学校读者我要写书评

暂无评论

Synthesizing Filtering Algorithms for Global Chance-constraints

Synthesizing Filtering Algorithms for Global Chance-Constrai...

引用

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

作者： Hnich, Brahim Rossi, Roberto Tarim, S. Armagan Prestwich, Steven Izmir Univ Econ Fac Comp Sci Izmir Turkey Univ Wageningen & Res Ctr Logist Decis & Informat Sci Wageningen Netherlands Univ Nottingham Operat Management Div Nottingham England Univ Coll Cork Ireland Cork Constraint Computat Ctr Cork Ireland

ISBN: (纸本)9783642042430

Stochastic constraint Satisfaction Problems (SCSPs) are a powerful modeling framework for problems under uncertainty. To solve them is a P-Space task. the only solution approach to date compiles down SCSPs into classical CSPs. this allows the rouse of classical constraint solvers to solve SCSPs, but at the cost of increased space requirements and weak constraint propagation. this paper tries to overcome some of these drawbacks by automatically synthesizing filtering algorithms for global chance-constraints. these filtering algorithms are parameterized by propagators for the deterministic version of the chance-constraints. this approach allows the rouse of existing propagators in current, constraint solvers and it enhances constraint propagation. Experiments show the benefits of this novel approach.

关键词： constraint satisfaction problems

来源：评论

学校读者我要写书评

暂无评论

Global cut framework for removing symmetries 1

引用

7th international conference on principles and practice of constraint programming, cp 2001

作者： Focacci, Filippo Milano, Michaela ILOG S.A 9 rue de Verdun BP 85 GentillyF-94253 France DEIS University of Bologna V.le Risorgimento 2 40136 Italy

ISBN: (数字)9783540455783

ISBN: (纸本)3540428631

In this paper, we propose a general technique for removing symmetries in CSPs during search. the idea is to record no-goods, during the exploration of the search tree, whose symmetric counterpart (if any) should be removed. the no-good, called Global Cut Seed (GCS), is used to generate Symmetry Removal Cuts (SRCs), i.e., constraints that are dynamically generated during search and hold in the entire search tree. the propagation of SRCs removes symmetric configurations with respect to already visited states. We present a general, correct and complete filtering algorithm for SRCs. the main advantages of the proposed approach are that it is not intrusive in the problem-dependent search strategy, treats symmetries in an additive way since GCSs are symmetry independent, and enables to write filtering algorithms which handle families of symmetries together. Finally, we show that many relevant previous approaches can be seen as special cases of our framework. © Springer-Verlag Berlin Heidelberg 2001.

关键词： constraint satisfaction problems

来源：评论

学校读者我要写书评

暂无评论

Tree-Decompositions with Connected Clusters for Solving constraint Networks

Tree-Decompositions with Connected Clusters for Solving Cons...

引用

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

作者： Jegou, Philippe Terrioux, Cyril Aix Marseille Univ LSIS UMR 7296 F-13397 Marseille France

ISBN: (纸本)9783319104287;9783319104270

From a theoretical viewpoint, the (tree-) decomposition methods offer a good approach for solving constraint Satisfaction Problems (CSPs) when their (tree)-width is small. In this case, they have often shown their practical interest. So, the literature (coming from Mathematics or AI) has concentrated its efforts on the minimization of a single parameter, the tree-width. Nevertheless, experimental studies have shown that this parameter is not always the most relevant to consider for solving CSPs. In this paper, we experimentally show that the decomposition algorithms of the state of the art produce clusters (a tree-decomposition is a tree of clusters) having several connected components. then we highlight that such clusters create a real problem for the efficiency of solving methods. To avoid this kind of problem, we consider here a new kind of graph decomposition called Bag-Connected Tree-Decomposition, which considers only tree-decompositions such that each cluster is connected. We propose a first polynomial time algorithm to find such decompositions. Finally, we show experimentally that using these bag-connected tree-decompositions improves significantly the solving of CSPs by decomposition methods.

关键词： Trees (mathematics)

来源：评论

学校读者我要写书评

暂无评论

Tractable clones of polynomials over semigroups

引用

11th international conference on principles and practice of constraint programming (cp 2005)

作者： Dalmau, V Gavaldà, R Tesson, P thérien, D Univ Pompeu Fabra Dept Tecnol Barcelona Spain Univ Politecn Cataluna LSI Dept Software Catalunya Spain Univ Laval Dept Informat & Genie Logiciel Quebec City PQ G1K 7P4 Canada McGill Univ Sch Comp Sci Montreal PQ H3A 2T5 Canada

ISBN: (纸本)3540292381

We contribute to the algebraic study of the complexity of constraint satisfaction problems. We give a new sufficient condition on a set of relations F over a domain S for the tractability of CSP(Gamma): if S is a block-group (a particular class of semigroups) of exponent omega and Gamma is a set of relations over S preserved by the operation defined by the polynomial f(x, y, z) = xy(omega-1)z over S, then CSP (F) is tractable. this theorem strictly improves on results of Feder and Vardi and Bulatov et al. and we demonstrate it by reproving an upper bound of Klima et al. We also investigate systematically the tractability of CSP(Gamma) when Gamma is a set of relations closed under operations that are all expressible as polynomials over a finite semigroup S. In particular, if S is a nilpotent group, we show that CSP(F) is tractable iff one of these polynomials defines a Malt'sev operation, and conjecture that this holds for all groups.

关键词： Polynomials

来源：评论

学校读者我要写书评

暂无评论

principles and practice of constraint programming 1

引用

丛书名： Lecture Notes in Computer Science

1000年

作者： Barry O’Sullivan

ISBN: (数字)9783319104287

ISBN: (纸本)9783319104270

this book constitutes the refereed conference proceedings of the 20th international conference on principles and practice of constraint programming, cp 2014, held in Lyon, France, in September 2014.;the 65 revised papers presented together with 4 invited talks were carefully selected from 108 submissions. the scope of cp 2014 includes all aspects of computing with constraints, including theory, algorithms, environments, languages, models, systems, and applications such as decision making, resource allocation, and agreement technologies.

关键词： Mathematical Logic and Formal Languages Mathematics of Computing Artificial Intelligence Algorithm Analysis and Problem Complexity

来源：评论

学校读者我要写书评

暂无评论

On Backdoors to Tractable constraint Languages

On Backdoors to Tractable Constraint Languages

引用

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

作者： Carbonnel, Clement Cooper, Martin C. Hebrard, Emmanuel CNRS LAAS 7 Ave Colonel Roche F-31400 Toulouse France Univ Toulouse 3 Inst Rech Informat Toulouse F-31062 Toulouse France Univ Toulouse 1 INP Toulouse F-31400 Toulouse France

ISBN: (纸本)9783319104287;9783319104270

In the context of CSPs, a strong backdoor is a subset of variables such that every complete assignment yields a residual instance guaranteed to have a specified property. If the property allows efficient solving, then a small strong backdoor provides a reasonable decomposition of the original instance into easy instances. An important challenge is the design of algorithms that can find quickly a small strong backdoor if one exists. We present a systematic study of the parameterized complexity of backdoor detection when the target property is a restricted type of constraint language defined by means of a family of polymorphisms. In particular, we show that under the weak assumption that the polymorphisms are idempotent, the problem is unlikely to be FPT when the parameter is either r (the constraint arity) or k (the size of the backdoor) unless P = NP or FPT = W[2]. When the parameter is k + r, however, we are able to identify large classes of languages for which the problem of finding a small backdoor is FPT.

关键词： constraint satisfaction problems

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：