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

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

作者： Loth, Manuel Sebag, Michele Hamadi, Youssef Schoenauer, Marc Microsoft Res INRIA Joint Ctr Palaiseau France Univ Paris Sud LRI TAO CNRSINRIA Orsay France Microsoft Res Cambridge England

ISBN: (纸本)9783642406263;9783642406270

constraint programming (CP) solvers classically explore the solution space using tree-search based heuristics. Monte-Carlo Tree Search (MCTS), aimed at optimal sequential decision making under uncertainty, gradually grows a search tree to explore the most promising regions according to a specified reward function. At the crossroad of CP and MCTS, this paper presents the Bandit Search for constraint programming (BASCOP) algorithm, adapting MCTS to the specifics of the CP search. this contribution relies on i) a generic reward function suited to CP and compatible with a multiple restart strategy;ii) the use of depth-first search as roll-out procedure in MCTS. BASCOP, on the top of the Gecode constraint solver, is shown to significantly improve on depth-first search on some CP benchmark suites, demonstrating its relevance as a generic yet robust CP search method.

关键词： adaptive search value selection bandit UCB MCTS

来源：评论

学校读者我要写书评

暂无评论

constraint Based Computation of Periodic Orbits of Chaotic Dynamical Systems

Constraint Based Computation of Periodic Orbits of Chaotic D...

引用

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

作者： Goldsztejn, Alexandre Granvilliers, Laurent Jermann, Christophe CNRS LINA UMR 6241 2 Rue Houssiniere F-44300 Nantes France Univ Nantes LINA UMR 6241 F-44035 Nantes France

ISBN: (纸本)9783642406263;9783642406270

the chaos theory emerged at the end of the 19th century, and it has given birth to a deep mathematical theory in the 20th century, with a strong practical impact (e. g., weather forecast, turbulence analysis). Periodic orbits play a key role in understanding chaotic systems. their rigorous computation provides some insights on the chaotic behavior of the system and it enables computer assisted proofs of chaos related properties (e. g., topological entropy). In this paper, we show that the (numerical) constraint programming framework provides a very convenient and efficient method for computing periodic orbits of chaotic dynamical systems: Indeed, the flexibility of CP modeling allows considering various models as well as including additional constraints (e. g., symmetry breaking constraints). Furthermore, the richness of the different solving techniques (tunable local propagators, search strategies, etc.) leads to highly efficient computations. these strengths of the CP framework are illustrated by experimental results on classical chaotic systems from the literature.

关键词： Chaotic dynamical systems periodic orbits topological entropy numerical constraint satisfaction symmetry breaking

来源：评论

学校读者我要写书评

暂无评论

constraint-Based Approaches for Balancing Bike Sharing Systems

Constraint-Based Approaches for Balancing Bike Sharing Syste...

引用

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

作者： Di Gaspero, Luca Rendl, Andrea Urli, Tommaso Univ Udine DIEGM Via Sci 206 I-33100 Udine Italy Austrian Inst Technol Mobility Dept Dynam Transport Syst Vienna Austria

In order to meet the users9; demand, bike sharing systems must be regularly rebalanced. the problem of balancing bike sharing systems (BBSS) is concerned with designing optimal tours and operating instructions for ... 详细信息

ISBN: (纸本)9783642406263;9783642406270

In order to meet the users' demand, bike sharing systems must be regularly rebalanced. the problem of balancing bike sharing systems (BBSS) is concerned with designing optimal tours and operating instructions for relocating bikes among stations to maximally comply with the expected future bike demands. In this paper, we tackle the BBSS by means of constraint programming: first, we introduce two novel constraint models for the BBSS including a smart branching strategy that focusses on the most promising routes. Second, in order to speed-up the search process, we incorporate both models in a Large Neighborhood Search (LNS) approach that is adapted to the respective CP model. third, we perform a computational evaluation on instances based on real-world data, where we see that the LNS approach outperforms the Branch & Bound approach and is competitive with other existing approaches.

关键词： Bicycles

来源：评论

学校读者我要写书评

暂无评论

Breaking Symmetry with Different Orderings

Breaking Symmetry with Different Orderings

引用

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

作者： Narodytska, Nina Walsh, Toby NICTA Sydney NSW Australia UNSW Sydney NSW Australia

ISBN: (纸本)9783642406263;9783642406270

We can break symmetry by eliminating solutions within each symmetry class. For instance, the Lex-Leader method eliminates all but the smallest solution in the lexicographical ordering. Unfortunately, the Lex-Leader method is intractable in general. We prove that, under modest assumptions, we cannot reduce the worst case complexity of breaking symmetry by using other orderings on solutions. We also prove that a common type of symmetry, where rows and columns in a matrix of decision variables are interchangeable, is intractable to break when we use two promising alternatives to the lexicographical ordering: the Gray code ordering (which uses a different ordering on solutions), and the Snake-Lex ordering (which is a variant of the lexicographical ordering that re-orders the variables). Nevertheless, we show experimentally that using other orderings like the Gray code to break symmetry can be beneficial in practice as they may better align with the objective function and branching heuristic.

关键词： constraint theory

来源：评论

学校读者我要写书评

暂无评论

Model Combinators for Hybrid Optimization

Model Combinators for Hybrid Optimization

引用

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

作者： Fontaine, Daniel Michel, Laurent Van Hentenryck, Pascal Univ Connecticut Storrs CT 06269 USA Univ Melbourne NICTA Melbourne Vic 3010 Australia

ISBN: (纸本)9783642406263;9783642406270

In recent years, CML, G12 and SIMPL, have achieved significant progress in automating the generation of hybrid solvers from high-level model specifications. this paper pushes this research direction one step further and introduces the concept of model combinators to provide principled model compositions. these model combinators rely on runnables capturing executable models, runnable signatures that capture what runnables can produce and consume, and model hierarchies, which track relationships among models. these concepts make it possible to enforce the soundness of model compositions and to determine the best model compositions automatically. A prototype of the framework on top of the Objective-CP optimization system is presented.

关键词： constraint theory

来源：评论

学校读者我要写书评

暂无评论

Lifting Structural Tractability to CSP with Global constraints

Lifting Structural Tractability to CSP with Global Constrain...

引用

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

作者： thorstensen, Evgenij Univ Oxford Dept Comp Sci Oxford OX1 2JD England

ISBN: (纸本)9783642406263;9783642406270

A wide range of problems can be modelled as constraint satisfaction problems (CSPs), that is, a set of constraints that must be satisfied simultaneously. constraints can either be represented extensionally, by explicitly listing allowed combinations of values, or implicitly, by special-purpose algorithms provided by a solver. Such implicitly represented constraints, known as global constraints, are widely used;indeed, they are one of the key reasons for the success of constraint programming in solving real-world problems. In recent years, a variety of restrictions on the structure of CSP instances that yield tractable classes have been identified. However, many such restrictions fail to guarantee tractability for CSPs with global constraints. In this paper, we investigate the properties of extensionally represented constraints that these restrictions exploit to achieve tractability, and show that there are large classes of global constraints that also possess these properties. this allows us to lift these restrictions to the global case, and identify new tractable classes of CSPs with global constraints.

关键词： constraint satisfaction problems

来源：评论

学校读者我要写书评

暂无评论

Modelling Destructive Assignments

Modelling Destructive Assignments

引用

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

作者： Francis, Kathryn Navas, Jorge Stuckey, Peter J. Natl ICT Australia Victoria Res Lab Melbourne Vic 3010 Australia Univ Melbourne Melbourne Vic 3010 Australia

ISBN: (纸本)9783642406263;9783642406270

Translating procedural object oriented code into constraints is required for many processes that reason about the execution of this code. the most obvious is for symbolic execution of the code, where the code is executed without necessarily knowing the concrete values. In this paper, we discuss translations from procedural object oriented code to constraints in the context of solving optimisation problems defined via simulation. A key difficulty arising in the translation is the modelling of state changes. We introduce a new technique for modelling destructive assignments that outperforms previous approaches. Our results show that the optimisation models generated by our technique can be as efficient as equivalent hand written models.

关键词： Computer programming

来源：评论

学校读者我要写书评

暂无评论

Asynchronous Forward Bounding Revisited

Asynchronous Forward Bounding Revisited

引用

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

作者： Wahbi, Mohamed Ezzahir, Redouane Bessiere, Christian Mines Nantes TASC INRIA CNRS Mines Nantes France Univ Ibn Zohr Natl Sch Appl Sci Rabat Morocco Univ Montpellier Montpellier France

ISBN: (纸本)9783642406263;9783642406270

the Distributed constraint Optimization Problem (DCOP) is a powerful framework for modeling and solving applications in multi-agent coordination. Asynchronous Forward Bounding (AFB_BJ) is one of the best algorithms to solve DCOPs. We propose AFB_BJ(+), a revisited version of AFB_BJ in which we refine the lower bound computations. We also propose to compute lower bounds for the whole domain of the last assigned agent instead of only doing this for its current assignment. this reduces both the number of messages needed and the time future agents remain idle. In addition, these lower bounds can be used as a value ordering heuristic in AFB_BJ(+). the experimental evaluation on standard benchmark problems shows the efficiency of AFB_BJ(+) compared to other algorithms for DCOPs.

关键词： Computer programming

来源：评论

学校读者我要写书评

暂无评论

ASP with non-herbrand partial functions: a language and system for practical use

引用

thEORY AND practice OF LOGIC programming 2013年第4-5期13卷 547-561页

作者： Balduccini, Marcello Eastman Kodak Co Rochester NY 14650 USA

Dealing with domains involving substantial quantitative information in Answer Set programming (ASP) often results in cumbersome and inefficient encodings. Hybrid "CASP" languages combining ASP and constraint programming aim to overcome this limitation, but also impose inconvenient constraints - first and foremost that quantitative information must be encoded by means of total functions. this goes against central knowledge representation principles that contribute to the power of ASP, and makes the formalization of certain domains difficult. ASP{f} is being developed with the ultimate goal of providing scientists and practitioners with an alternative to CASP languages that allows for the efficient representation of qualitative and quantitative information in ASP without restricting one's ability to deal with incompleteness or uncertainty. In this paper we present the latest outcome of such research: versions of the language and of the supporting system that allow for practical, industrial-size use and scalability. the applicability of ASP{f} is demonstrated by a case study on an actual industrial application.

关键词： Answer Set programming non-herbrand functions constraint answer set programming practical applications

来源：评论

学校读者我要写书评

暂无评论

Answer Set programming: Boolean constraint Solving for Knowledge Representation and Reasoning

Answer Set Programming: Boolean Constraint Solving for Knowl...

引用

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

作者： Schaub, Torsten Simon Fraser Univ Burnaby BC V5A 1S6 Canada

ISBN: (纸本)9783642406263;9783642406270

Answer Set programming (ASP; [1,2,3]) is a declarative problem solving approach, combining a rich yet simple modeling language with high-performance Boolean constraint solving capacities. ASP is particularly suited for modeling problems in the area of Knowledge Representation and Reasoning involving incomplete, inconsistent, and changing information. As such, it offers, in addition to satisfiability testing, various reasoning modes, including different forms of model enumeration, intersection or unioning, as well as multi-criteria and -objective optimization. From a formal perspective, ASP allows for solving all search problems in NP (and NP NP ) in a uniform way. Hence, ASP is wellsuited for solving hard combinatorial search problems, like system design and timetabling. Prestigious applications of ASP include composition of Renaissance music [4], decision support systems for NASA shuttle controllers [5], reasoning tools in systems biology [6,7,8] and robotics [9,10], industrial team-building [11], and many more. the versatility of ASP is nicely reflected by the ASP solver clasp [12], winning first places at various solver competitions, such as ASP,MISC, PB, and SAT competitions. the solver clasp is at the heart of the open source platform Potassco hosted at *** . Potassco stands for the “Potsdam Answer Set Solving Collection-[13] and has seen more than 30000 downloads world-wide since its inception at the end of 2008. the talk will start with an introduction to ASP, its modeling language and solving methodology, and portray some distinguished ASP systems.

关键词： Problem solving

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：