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

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

作者： Wilson, Nic Grimes, Diarmuid Freuder, Eugene C. Natl Univ Ireland Univ Coll Cork Cork Constraint Comp Ctr Dept Comp Sci Cork Ireland

ISBN: (纸本)9783540749691

We consider constraint Satisfaction Problems in which constraints can be initially incomplete, where it is unknown whether certain tuples satisfy the constraint or not. We assume that we can determine such an unknown tuple, i.e., find out whether this tuple is in the constraint or not, but doing so incurs a known cost, which may vary between tuples. We also assume that we know the probability of an unknown tuple satisfying a constraint. We define algorithms for this problem, based on backtracking search. Specifically, we consider a simple iterative algorithm based on a cost limit on which unknowns may be determined, and a more complex algorithm that delays determining an unknown in order to estimate better whether doing so is worthwhile. We show experimentally that the more sophisticated algorithms can greatly reduce the average cost.

关键词： Problem solving

来源：评论

学校读者我要写书评

暂无评论

Integration of Structural constraints into TSP Models 25th

Integration of Structural Constraints into TSP Models

引用

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

作者： Isoart, Nicolas Regin, Jean-Charles Univ Cote Azur CNRS I3S Sophia Antipolis France

ISBN: (纸本)9783030300487

Several models based on constraint programming have been proposed to solve the traveling salesman problem (TSP). the most efficient ones, such as the weighted circuit constraint (WCC), mainly rely on the Lagrangian relaxation of the TSP, based on the search for spanning tree or more precisely "1-tree". the weakness of these approaches is that they do not include enough structural constraints and are based almost exclusively on edge costs. the purpose of this paper is to correct this drawback by introducing the Hamiltonian cycle constraint associated with propagators. We propose some properties preventing the existence of a Hamiltonian cycle in a graph or, conversely, properties requiring that certain edges be in the TSP solution set. Notably, we design a propagator based on the research of k-cutsets. the combination of this constraint with the WCC constraint allows us to obtain, for the resolution of the TSP, gains of an order of magnitude for the number of backtracks as well as a strong reduction of the computation time.

关键词： Global constraint TSP Propagator

来源：评论

学校读者我要写书评

暂无评论

Guarded constraint Models Define Treewidth Preserving Reductions 25th

Guarded Constraint Models Define Treewidth Preserving Reduct...

引用

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

作者： Mitchell, David Simon Fraser Univ Vancouver BC Canada

ISBN: (纸本)9783030300487

Combinatorial problem solving is often carried out by reducing problems to SAT or some other finite domain constraint language. Explicitly defining reductions can be avoided by using so-called "model and solve" systems. In this case the user writes a declarative problem specification in a constraint modelling language, such as MiniZinc. the specification implicitly defines a reduction, which is implemented by the constraint solving system. Unfortunately, reductions can destroy useful instance structure, such has having small treewidth. We show that reductions defined by certain guarded first order formulas preserve bounded treewidth. We also show such reductions can be executed automatically from problem specifications written in a guarded existential second order logic (there exists SO) by simple grounding or "flattening" algorithms. Many constraint modelling languages are essentially extensions of there exists SO, and this result applies to natural, useful, fragments of these languages.

关键词： constraint modelling language Reduction Treewidth

来源：评论

学校读者我要写书评

暂无评论

constraint programming-Based Job Dispatching for Modern HPC Applications 25th

Constraint Programming-Based Job Dispatching for Modern HPC ...

引用

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

作者： Galleguillos, Cristian Kiziltan, Zeynep Sirbu, Alina Babaoglu, Ozalp Pontificia Univ Catolica Valparaiso Valparaiso Chile Univ Bologna Bologna Italy Univ Pisa Pisa Italy

ISBN: (纸本)9783030300487

HPC systems are increasingly being used for big data analytics and predictive model building that employ many short jobs. In these application scenarios, HPC job dispatchers need to process large numbers of short jobs quickly and make decisions on-line while ensuring high Quality-of-Service (QoS) levels and meet demanding timing requirements. constraint programming (cp) is an effective approach for tackling job dispatching problems. Yet, the state-of-the-art cp-based job dispatchers are unable to satisfy the challenges of on-line dispatching and take advantage of job duration predictions. these limitations jeopardize achieving high QoS levels, and consequently impede the adoption of cp-based dispatchers in HPC systems. We propose a class of cp-based dispatchers that are more suitable for HPC systems running modern applications. the new dispatchers are able to reduce the time required for generating on-line dispatching decisions significantly, and are able to make effective use of job duration predictions to decrease waiting times and job slowdowns, especially for workloads dominated by short jobs.

关键词： Quality of service

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Improvement of the Embarrassingly Parallel Search for Data Centers

Improvement of the Embarrassingly Parallel Search for Data C...

引用

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

作者： Regin, Jean-Charles Rezgui, Mohamed Malapert, Arnaud Univ Nice Sophia Antipolis CNRS I3S UMR 7271 F-06900 Sophia Antipolis France

ISBN: (纸本)9783319104287;9783319104270

We propose an adaptation of the Embarrassingly Parallel Search (EPS) method for data centers. EPS is a simple but efficient method for parallel solving of CSPs. EPS decomposes the problem in many distinct subproblems which are then solved independently by workers. EPS performed well on multicores machines (40), but some issues arise when using more cores in a datacenter. Here, we identify the decomposition as the cause of the degradation and propose a parallel decomposition to address this issue. thanks to it, EPS gives almost linear speedup and outperforms work stealing by orders of magnitude using the Gecode solver.

关键词： constraint satisfaction problems

来源：评论

学校读者我要写书评

暂无评论

Solving Intensional Weighted CSPs by Incremental Optimization with BDDs

Solving Intensional Weighted CSPs by Incremental Optimizatio...

引用

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

作者： Bofill, Miquel Palahi, Miquel Suy, Josep Villaret, Mateu Univ Girona Dept Informat Matemat Aplicada & Estat Girona Spain

ISBN: (纸本)9783319104287;9783319104270

We present a method for solving weighted constraint Satisfaction Problems, based on translation into a constraint Optimization Problem and iterative calls to an SMT solver, with successively tighter bounds of the objective function. the novelty of the method herewith described lies in representing the bound constraint as a shared Binary Decision Diagram, which in turn is translated into SAT. this offers two benefits: first, BDDs built for previous bounds can be used to build the BDDs for new (tighter) bounds, considerably reducing the BDD construction time;second, as a by-product, many clauses asserted to the solver in previous iterations can be reused. the reported experimentation on the WSimply system shows that this technique has better performance in general than other methods implemented in the system. Moreover, with the new technique WSimply outperforms some state-of-the-art solvers in most of the studied instances.

关键词： constraint satisfaction problems

来源：评论

学校读者我要写书评

暂无评论

Challenges for constraint programming in networking

引用

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

作者： Simonis, H Univ London Imperial Coll Sci Technol & Med IC Parc London SW7 2AZ England Parc Technol Ltd London England

ISBN: (纸本)3540232419

In this talk we present a number of problems for network design, planning and analysis and show how they can be addressed with different hybrid cp solutions. Clearly, this problem domain is of huge practical importance, but it also provides us with interesting, complex problem structures. cp directly competes with MILP and local search approaches to these problems, with best results often obtained by a combination of different solution techniques. Teams at Parc Technologies and IC-Parc have been working in this field over the last years, with a number of applications now embedded in commercial products.

关键词： constraint programming

来源：评论

学校读者我要写书评

暂无评论

Revisiting the sequence constraint

Revisiting the sequence constraint

引用

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

作者： van Hoeve, Willem-Jan Pesant, Gilles Rousseau, Louis-Martin Sabharwal, Ashish Cornell Univ Dept Comp Sci Ithaca NY 14853 USA Ecole Polytech Montreal PQ H3C 3A7 Canada Univ Montreal Ctr Res Transportat Montreal PQ H3C 3J7 Canada

ISBN: (纸本)3540462678

Many 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 width. To date, none of the filtering algorithms proposed guaranteed domain consistency. In this paper, we present three filtering algorithms for the sequence constraint, with 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. Our customized algorithm does so in polynomial time, and can even be applied to a generalized sequence constraint for subsequences of variable widths. Experimental results show the practical usefulness of each.

关键词： constraint theory

来源：评论

学校读者我要写书评

暂无评论

constraint-Based Local Search for the Automatic Generation of Architectural Tests

Constraint-Based Local Search for the Automatic Generation o...

引用

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

作者： Van Hentenryck, Pascal Coffrin, Carleton Gutkovich, Boris Brown Univ Providence RI 02912 USA Intel Corp Haifa Israel

ISBN: (纸本)9783642042430

this paper considers the automatic generation of architectural tests (ATGP), a fundamental problem in processor validation. ATGPs are complex conditional constraint satisfaction problems which typically feature both hard and soft constraints and very large domains (e.g., all memory addresses). Moreover, the goal is to generate a. large number of diverse Solutions under tight runtime constraints. To improve solution diversity, this paper proposes a, novel approach to ATGPs by modeling them as MAXDIVERSEkSET problems and solving them with constraint-based local search over conditional variables. the paper presents the semantics and implementation of Conditional variables in this context and demonstrates the computational benefits of the approach.

关键词： Semantics

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：