the proceedings contain 63 papers. the topics discussed include: a parametric approach for smaller and better encodings of cardinality constraints;automated symmetry breaking and model selection in conjure;MinSAT vers...
ISBN:
(纸本)9783642406263
the proceedings contain 63 papers. the topics discussed include: a parametric approach for smaller and better encodings of cardinality constraints;automated symmetry breaking and model selection in conjure;MinSAT versus MaxSAT for optimization problems;counting spanning trees to guide search in constrained spanning tree problems;tractable combinations of global constraints;postponing optimization to speed up MAXSAT solving;solving weighted CSPs by successive relaxations;constraint-based program reasoning with heaps and separation;model combinators for hybrid optimization;a simple and effective decomposition for the multidimensional binpacking constraint;maintaining soft arc consistencies in BnB-ADOPT+ during search;solving string constraints: the case for constraintprogramming;blowing holes in various aspects of computational problems, with applications to constraint satisfaction;and focused random walk with configuration checking and break minimum for satisfiability.
In a previous work, we introduced a filtering for the Bin-Packing constraint based on a cardinality reasoning for each bin combined with a global cardinality constraint. We improve this filtering with an algorithm pro...
详细信息
ISBN:
(纸本)9783642406263;9783642406270
In a previous work, we introduced a filtering for the Bin-Packing constraint based on a cardinality reasoning for each bin combined with a global cardinality constraint. We improve this filtering with an algorithm providing tighter bounds on the cardinality variables. We experiment it on the Balanced Academic Curriculum Problems demonstrating the benefits of the cardinality reasoning for such bin-packing problems.
We propose a new filtering algorithm for the cumulative constraint. It applies the Edge-Finding, the Extended-Edge-Finding and the Time-Tabling rules in O(kn log n) where k is the number of distinct task heights. By a...
详细信息
ISBN:
(纸本)9783642406263;9783642406270
We propose a new filtering algorithm for the cumulative constraint. It applies the Edge-Finding, the Extended-Edge-Finding and the Time-Tabling rules in O(kn log n) where k is the number of distinct task heights. By a proper use of tasks decomposition, it enforces the Time-Tabling rule and the Time-Table Extended-Edge-Finding rule. thus our algorithm improves upon the best known Extended-Edge-Finding propagator by a factor of O(log n) while achieving a much stronger filtering.
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.
the multibin_packing constraint captures a fundamental substructure of many assignment problems, where a set of items, each with a fixed number of dimensions, must be assigned to a number of bins with limited capaciti...
详细信息
ISBN:
(纸本)9783642406263;9783642406270
the multibin_packing constraint captures a fundamental substructure of many assignment problems, where a set of items, each with a fixed number of dimensions, must be assigned to a number of bins with limited capacities. In this work we propose a simple decomposition for multibin_packing that uses a bin packing constraint for each dimension, a set of all different constraints automatically derived from a conflict graph, plus two alternative symmetry breaking approaches. Despite its simplicity, the proposed decomposition is very effective on a number of instances recently proposed in the literature.
We improve an existing propagator for the context-free grammar constraint and demonstrate experimentally the practicality of the resulting propagator. the underlying technique could be applied to other existing propag...
详细信息
ISBN:
(纸本)9783642406263;9783642406270
We improve an existing propagator for the context-free grammar constraint and demonstrate experimentally the practicality of the resulting propagator. the underlying technique could be applied to other existing propagators for this constraint. We argue that constraintprogramming solvers are more suitable than existing solvers for verification tools that have to solve string constraints, as they have a rich tradition of constraints for membership in formal languages.
Large neighborhood search (LNS) [25] is a framework that combines the expressiveness of constraintprogramming withthe efficiency of local search to solve combinatorial optimization problems. this paper introduces an...
详细信息
ISBN:
(纸本)9783642406263;9783642406270
Large neighborhood search (LNS) [25] is a framework that combines the expressiveness of constraintprogramming withthe 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.
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.
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.
Counting-based branching heuristics such as maxSD were shown to be effective on a variety of constraint satisfaction problems. these heuristics require that we equip each family of constraints with a dedicated algorit...
详细信息
ISBN:
(纸本)9783642406263;9783642406270
Counting-based branching heuristics such as maxSD were shown to be effective on a variety of constraint satisfaction problems. these heuristics require that we equip each family of constraints with a dedicated algorithm to compute the local solution density of variable assignments, much as what has been done with filtering algorithms to apply local inference. this paper derives an exact polytime algorithm to compute solution densities for a spanning tree constraint, starting from a known result about the number of spanning trees in a graph. We then empirically compare branching heuristics based on that result with other generic heuristics.
暂无评论