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

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)

作者： Lagerkvist, Victor Wahlstrom, Magnus Tech Univ Dresden Inst Algebra Dresden Germany Royal Holloway Univ London Dept Comp Sci Egham Surrey England

ISBN: (纸本)9783319661582;9783319661575

A kernelization algorithm for a computational problem is a procedure which compresses an instance into an equivalent instance whose size is bounded with respect to a complexity parameter. For the constraint satisfaction problem (CSP), there exist many results concerning upper and lower bounds for kernelizability of specific problems, but it is safe to say that we lack general methods to determine whether a given problem admits a kernel of a particular size. In this paper, we take an algebraic approach to the problem of characterizing the kernelization limits of NP-hard CSP problems, parameterized by the number of variables. Our main focus is on problems admitting linear kernels, as has, somewhat surprisingly, previously been shown to exist. We show that a finite-domain CSP problem has a kernel with O(n) constraints if it can be embedded (via a domain extension) into a CSP which is preserved by a Maltsev operation. this result utilise a variant of the simple algorithm for Maltsev constraints. In the complementary direction, we give indication that the Maltsev condition might be a complete characterization for Boolean CSPs with linear kernels, by showing that an algebraic condition that is shared by all problems with a Maltsev embedding is also necessary for the existence of a linear kernel unless NP subset of co-NP/poly.

关键词： constraint satisfaction problems

来源：评论

学校读者我要写书评

暂无评论

CPBPV: a constraint-programming framework for bounded program verification

引用

constraintS 2010年第2期15卷 238-264页

作者： Collavizza, Helene Rueher, Michel Van Hentenryck, Pascal Univ Nice Sophia Antipolis CNRS I3S F-06903 Sophia Antipolis France Brown Univ Providence RI 02912 USA

this paper studies how to verify the conformity of a program with its specification and proposes a novel constraint-programming framework for bounded program verification (CPBPV). the CPBPV framework uses constraint stores to represent both the specification and the program and explores execution paths of bounded length nondeterministically. the CPBPV framework detects non-conformities and provides counter examples when a path of bounded length that refutes some properties exists. the input program is partially correct under the boundness restrictions, if each constraint store so produced implies the post-condition. CPBPV does not explore spurious execution paths, as it incrementally prunes execution paths early by detecting that the constraint store is not consistent. CPBPV uses the rich language of constraint programming to express the constraint store. Finally, CPBPV is parameterized with a list of solvers which are tried in sequence, starting with the least expensive and less general. Experimental results often produce orders of magnitude improvements over earlier approaches, running times being often independent of the size of the variable domains. Moreover, CPBPV was able to detect subtle errors in some programs for which other frameworks based on bounded model checking have failed.

关键词： Bounded program verification constraint-based symbolic execution Detection of nonconformities Test cases generation

来源：评论

学校读者我要写书评

暂无评论

Random constraint satisfaction: theory meets practice 4th

引用

4th international conference on principles and practice of constraint programming (CP 98)

作者： MacIntyre, E Prosser, P Smith, B Walsh, T Univ Strathclyde APES Res Grp Dept Comp Sci Glasgow Lanark Scotland Univ Leeds Sch Comp Studies APES Res Grp Leeds LS2 9JT W Yorkshire England

ISBN: (纸本)3540652248

We study the experimental consequences of a recent theoretical result by Achlioptas et al. that shows that conventional models of random problems are trivially insoluble in the limit. We survey the literature to identify experimental studies that lie within the scope of this result. We then estimate theoretically and measure experimentally the size at which problems start to become trivially insoluble. Our results demonstrate that most (but not all) of these experimental studies are luckily unaffected by this result. We also study an alternative model of random problems that does not suffer from this asymptotic weakness. We show that, at a typical problem size used in experimental studies, this model looks similar to conventional models. Finally, we generalize this model so that we can independently adjust the constraint tightness and density.

关键词： constraint theory

来源：评论

学校读者我要写书评

暂无评论

Continuous Casting Scheduling with constraint programming

Continuous Casting Scheduling with Constraint Programming

引用

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

作者： Gay, Steven Schaus, Pierre De Smedt, Vivian Catholic Univ Louvain Louvain Belgium PSI Met Dusseldorf Belgium

ISBN: (纸本)9783319104287;9783319104270

Although the Steel Mill Slab problem (prob 38 of CSPLib) has already been studied by the CP community, this approach is unfortunately not used anymore by steel producers since last century. Continuous casting is preferred instead, allowing higher throughput and better steel quality. this paper presents a CP model related to scheduling of operations for steel making with continuous casting. Activities considered range from the extraction of iron in the furnace to its casting in continuous casters. We describe the problem, detail a CP scheduling model that is finally used to solve real-life instances of some of the PSI Metals' customers.

关键词： Continuous Casting Steel Production Scheduling constraint programming

来源：评论

学校读者我要写书评

暂无评论

A Coinduction Rule for Entailment of Recursively Defined Properties

引用

14th international conference on principles and practice of constraint programming (CP 2008)

作者： Jaffar, Joxan Santosa, Andrew E. Voicu, Razvan Natl Univ Singapore Sch Comp Singapore 117543 Singapore

ISBN: (纸本)9783540859574

Recursively defined properties are ubiquitous. We present a proof method for establishing entailment G satisfies H of such properties G and H over a set of common variables. the main contribution is a particular proof rule based intuitively upon the concept of coinduction. this rule allows the inductive step of assuming that tin entailment holds during the proof the entailment. In general, the proof method is based on an unfolding (and no folding) algorithm that reduces recursive definitions to a point where only constraint solving is necessary. the constraint-based proof obligation is then discharged with available solvers. the algorithm executes the proof-by a search-based method which automatically discovers the opportunity of applying induction instead of the user having to specify some induction schema, and which does not require any base case.

关键词： Logic programming

来源：评论

学校读者我要写书评

暂无评论

On Testing constraint Programs

On Testing Constraint Programs

引用

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

作者： Lazaar, Nadjib Gotlieb, Arnaud Lebbah, Yahia INRIA Rennes Bretagne Atlantique Campus Beaulieu F-35042 Rennes France Univ Oran Es Senia LITIO Orange NSW Australia Univ Nice Sophia Antipolis Antipolis France

ISBN: (纸本)9783642153952

the success of several constraint-based modeling languages such as OPL, ZINC, or COMET, appeals for better software engineering practices, particularly in the testing phase. this paper introduces a testing framework enabling automated test case generation for constraint programming. We propose a general framework of constraint program development which supposes that a first declarative and simple constraint model is available from the problem specifications analysis. then, this model is refined using classical techniques such as constraint reformulation, surrogate and global constraint addition, or symmetry-breaking to form an improved constraint model that must be thoroughly tested before being used to address real-sized problems. We think that most of the faults are introduced in this refinement step and propose a process which takes the first declarative model as an oracle for detecting non-conformities. We derive practical test purposes from this process to generate automatically test data that exhibit non-conformities. We implemented this approach in a new tool called CPTEST that was used to automatically detect non-conformities on two classical benchmark programs, namely the Golomb rulers and the car-sequencing problem.

关键词： Modeling languages

来源：评论

学校读者我要写书评

暂无评论

constraint Handling in Flight Planning 23rd

Constraint Handling in Flight Planning

引用

作者： Knudsen, Anders Nicolai Chiarandini, Marco Larsen, Kim S. Univ Southern Denmark Dept Math & Comp Sci Campusvej 55 DK-5230 Odense M Denmark

ISBN: (纸本)9783319661582;9783319661575

Flight routes are paths in a network, the nodes of which represent waypoints in a 3D space. A common approach to route planning is first to calculate a cheapest path in a 2D space, and then to optimize the flight cost in the third dimension. We focus on the problem of finding a cheapest path through a network describing the 2D projection of the 3D waypoints. In European airspaces, traffic flow is handled by heavily constraining the flight network. the constraints can have very diverse structures, among them a generalization of the forbidden pairs type. they invalidate the FIFO property, commonly assumed in shortest path problems. We formalize the problem and provide a framework for the description, representation and propagation of the constraints in path finding algorithms, best-first, and A* search. In addition, we study a lazy approach to deal with the constraints. We conduct an experimental evaluation based on real-life data and conclude that our techniques for constraint propagation work best together with an iterative search approach, in which only constraints that are violated in previously found routes are introduced in the constraint set before the search is restarted.

关键词： Iterative methods

来源：评论

学校读者我要写书评

暂无评论

Multi-Objective Large Neighborhood Search

Multi-Objective Large Neighborhood Search

引用

19th Annual international conference on principles and practice of constraint programming (CP)

作者： Schaus, Pierre Hartert, Renaud UCLouvain ICTEAM B-1348 Louvain Belgium

ISBN: (纸本)9783642406263;9783642406270

Large neighborhood search (LNS) [25] is a framework that combines the expressiveness of constraint programming with the efficiency of local search to solve combinatorial optimization problems. this paper introduces an extension of LNS, called multi-objective LNS (MO-LNS), to solve multi-objective combinatorial optimization problems ubiquitous in practice. the idea of MO-LNS is to maintain a set of nondominated solutions rather than just one best-so-far solution. At each iteration, one of these solutions is selected, relaxed and optimized in order to strictly improve the hypervolume of the maintained set of nondominated solutions. We introduce modeling abstractions into the OscaR solver for MO-LNS and show experimentally the efficiency of this approach on various multi-objective combinatorial optimization problems.

关键词： constraint programming Multi-Objective Combinatorial Optimization Large Neighborhood Search

来源：评论

学校读者我要写书评

暂无评论

Modelling CSP solution algorithms with Petri decision nets 4th

引用

4th international conference on principles and practice of constraint programming (CP 98)

作者： Pontow, S Tech Univ Hamburg Harburg Dept Proc Automat Techniques D-21071 Hamburg Germany

ISBN: (纸本)3540652248

the constraint paradigm provides powerful concepts to represent and solve different kinds of planning problems. Typically a large and conflicting set of restrictions, objectives and preferences has to be considered for real planning problems. We introduce a unified formalism - called Petri decision nets -for representation and implementation of complex CSP solution algorithms. the formalism enables the consideration of the problem structure as well as given objectives and the usage of problem specific heuristics or expert knowledge. It is based on the fundamental assumption that designing CSP solution algorithms means designing decision networks.

关键词： constraint satisfaction problems

来源：评论

学校读者我要写书评

暂无评论

constraint techniques for solving the protein structure prediction problem 4th

引用

4th international conference on principles and practice of constraint programming (CP 98)

作者： Backofen, R LMU Munchen Inst Informat D-80538 Munich Germany

ISBN: (纸本)3540652248

the protein structure prediction problem is one of the most (if not the most) important problem in computational biology. this problem consists of finding the conformation of a protein (i.e., a sequence of amino-acids) with minimal energy. Because of the complexity of this problem, simplified models like Dill's HP-lattice model [12] have become a major tool for investigating general properties of protein folding. Even for this simplified model, the structure prediction problem has been shown to be NP-complete [3, 5]. We describe a constraint formulation of the HP-model structure prediction problem, present the basic constraints and search strategy. We then introduce a novel, general technique for excluding geometrical symmetries in constraint programming. To our knowledge, this is the first general and declarative technique for excluding symmetries in constraint programming that can be added to an existing implementation. Finally, we describe a new lower bound on the energy of an HP-protein. Both techniques yield an efficient pruning of the search tree.

关键词： Proteins

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：