Several types of symmetry have been identified and exploited in constraintprogramming, leading to large reductions in search time. We present a novel application of one such form of symmetry: detecting dynamic value ...
详细信息
ISBN:
(纸本)9783642406263;9783642406270
Several types of symmetry have been identified and exploited in constraintprogramming, leading to large reductions in search time. We present a novel application of one such form of symmetry: detecting dynamic value interchangeability in the random variables of a 2-stage stochastic problem. We use a real-world problem from the literature: finding an optimal investment plan to strengthen a transportation network, given that a future earthquake probabilistically destroys links in the network. Detecting interchangeabilities enables us to bundle together many equivalent scenarios, drastically reducing the size of the problem and allowing the exact solution of cases previously considered intractable and solved only approximately.
We consider a generic binary CSP solver parameterized by high-level design choices, i.e., backtracking mechanisms, constraint propagation levels, and variable ordering heuristics. We experimentally compare 24 differen...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
We consider a generic binary CSP solver parameterized by high-level design choices, i.e., backtracking mechanisms, constraint propagation levels, and variable ordering heuristics. We experimentally compare 24 different configurations of this generic solver on a benchmark of around a thousand instances. this allows us to understand the complementarity of the different search mechanisms, with an emphasis on Backtracking with Tree Decomposition (BTD). then, we use a per-instance algorithm selector to automatically select a good solver for each new instance to be solved. We introduce a new strategy for selecting the solvers of the portfolio, which aims at maximizing the number of instances for which the portfolio contains a good solver, independently from a time limit.
Novel search space splitting techniques have recently been successfully exploited to paralleliz constraintprogramming and Mixed Integer programming solvers. We first show how universal hashing can be used to extend o...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
Novel search space splitting techniques have recently been successfully exploited to paralleliz constraintprogramming and Mixed Integer programming solvers. We first show how universal hashing can be used to extend one such interesting approach to a generalized setting that goes beyond discrepancy-based search, while still retaining strong theoretical guarantees. We then explain that such static or explicit splitting approaches are not as effective in the context of parallel combinatorial search with intensive knowledge acquisition and sharing such as parallel SAT, where implicit splitting through clause sharing appears to dominate. Furthermore, we show that in a parallel setting there exists a surprising tradeoff between the well-known communication cost for knowledge sharing across multiple compute nodes and the so far neglected cost incurred by the computational load per node. We provide experimental evidence that one can successfully exploit this tradeoff and achieve reasonable speedups in parallel SAT solving beyond 16 cores.
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.
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.
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.
Computer trading systems are essential for today's financial markets where the trading systems' correctness is of paramount economical significance. Automated random testing is a useful technique to find bugs ...
详细信息
Set programming (ASP) is an expressive rule-based knowledge-representation formalism supported by efficient solver technology. Traditional evaluation of answer-set programs takes place in two phases: grounding and sol...
详细信息
ISBN:
(纸本)9781577358039
Set programming (ASP) is an expressive rule-based knowledge-representation formalism supported by efficient solver technology. Traditional evaluation of answer-set programs takes place in two phases: grounding and solving. Grounding incurs an up-to exponential increase in space, termed the grounding bottleneck of ASP, which is often encountered in practice. Lazy grounding avoids this bottleneck but is restricted to normal rules, significantly limiting the expressive power of this approach. We propose a framework to handle aggregates by normalizing them on demand during the lazy grounding process;we call this approach lazy normalization. It is feasible for different types of aggregates and can bring about up-to exponential gains in space and time.
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 ...
详细信息
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.
暂无评论