constraintprogramming (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 g...
详细信息
ISBN:
(纸本)9783642406263;9783642406270
constraintprogramming (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 constraintprogramming (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.
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). Periodi...
详细信息
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) constraintprogramming 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.
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 withthe expected future bike demands. In this paper, we tackle the BBSS by means of constraintprogramming: 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.
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 me...
详细信息
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 withthe objective function and branching heuristic.
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 a...
详细信息
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.
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 explici...
详细信息
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 constraintprogramming 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.
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 execu...
详细信息
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.
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...
详细信息
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 boththe 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.
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...
详细信息
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 constraintprogramming 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 principlesthat contribute to the power of ASP, and makes the formalization of certain domains difficult. ASP{f} is being developed withthe 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 (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 fo...
详细信息
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.
暂无评论