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.
Objective-CP is an optimization system that views an optimization program as the combination of a model, a search, and a solver. Models in Objective-CP follow the modeling style of constraintprogramming and are concr...
详细信息
ISBN:
(纸本)9783642406263;9783642406270
Objective-CP is an optimization system that views an optimization program as the combination of a model, a search, and a solver. Models in Objective-CP follow the modeling style of constraintprogramming and are concretized into specific solvers. Search procedures are specified in terms of high-level nondeterministic constructs, search combinators, and node selection strategies. Objective-CP supports fully transparent parallelization of multi-start and branch & bound algorithms. the implementation of Objective-CP is based on a sequence of model transformations, followed by a concretization step. Moreover, Objective-CP features a constraint-programming solver following a micro-kernel architecture for ease of maintenance and extensibility. Experimental results show the practicability of the approach.
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.
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.
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.
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.
We introduce a propagator for abstract pairs of Sum constraints, where the expressions in the sums respect a form of convexity. this propagator is parametric and can be instantiated for various concrete pairs, includi...
详细信息
ISBN:
(纸本)9783642406263;9783642406270
We introduce a propagator for abstract pairs of Sum constraints, where the expressions in the sums respect a form of convexity. this propagator is parametric and can be instantiated for various concrete pairs, including Deviation, Spread, and the conjunction of Sum and Count. We show that despite its generality, our propagator is competitive in theory and practice with state-of-the-art propagators.
constraintprogramming (CP) figures prominently in the process of functional hardware verification. the verification process is based on generating random tests according to given set of constraints. In this paper. we...
详细信息
ISBN:
(纸本)9783642406263;9783642406270
constraintprogramming (CP) figures prominently in the process of functional hardware verification. the verification process is based on generating random tests according to given set of constraints. In this paper. we introduce INTELLIGEN, a propagation based solver, and the random generator of Cadence's Specman verification tool. INTELLIGEN is designed to handle several problems beyond the mere need to find a feasible solution, including: generating random tests with a 'good' distribution over the solution space;maintaining test reproducibility through different run modes and minor code changes;and debug of the solving process by verification engineers. We discuss the advantages of CP solvers over other solving technologies (such as BDD, SAT or SMT), and how INTELLIGEN overcomes the disadvantages of CP.
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.
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.
暂无评论