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 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.
this paper considers the combination of berth and crane allocation problems in container terminals. We propose a novel approach based on constraintprogramming which is able to model many realistic operational constra...
详细信息
ISBN:
(纸本)9783642406263;9783642406270
this paper considers the combination of berth and crane allocation problems in container terminals. We propose a novel approach based on constraintprogramming which is able to model many realistic operational constraints. the costs for berth allocation, crane allocation, time windows, breaks and transition times during gang movements are optimized simultaneously. the model is based on a resource view where gangs are consumed by vessel activities. Side constraints are added independently around this core model. the model is richer than the state of the art in the operations research community. Experiments show that the model produces solutions with a cost gap of 1/10 (7,8%) to 1/5 (18,8%) compared to an ideal operational setting where operational constraints are ignored.
暂无评论