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.
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.
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.
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 generalization of the constraint satisfaction problem with universal quantifiers is a challenging PSPACE-complete problem, which is interesting theoretically and also relevant to solving other PSPACE problems aris...
详细信息
ISBN:
(纸本)3540292381
the generalization of the constraint satisfaction problem with universal quantifiers is a challenging PSPACE-complete problem, which is interesting theoretically and also relevant to solving other PSPACE problems arising in AI, such as reasoning with uncertainty, and multiplayer games. I define two new levels of consistency for QCSP, and give an algorithm to enforce consistency for one of these definitions. the algorithm is embedded in backtracking search, and tested empirically. the aims of this work are to increase the facilities available for modelling and to increase the power of constraint propagation for QCSPs. the work is motivated by examples from adversarial games.
In some recent works, a general framework for finite domains constraint satisfaction has been defined, where classical CSPs, fuzzy CSPs: weighted CSFs, partial CSPs and others can be easily cast. this framework, based...
详细信息
ISBN:
(纸本)3540652248
In some recent works, a general framework for finite domains constraint satisfaction has been defined, where classical CSPs, fuzzy CSPs: weighted CSFs, partial CSPs and others can be easily cast. this framework, based on a semiring structure: allows, under certain conditions: to compute are-consistency. Restricting to that case and integrating semiring-based constraint solving in the constraint Logic programming paradigm, we have implemented a generic language, clp(FD,S): for semiring-based constraint satisfaction. In this paper, we describe the kernel of the language: the SFD system and our implementation of clp(FD,S). We also give some performance results on various examples.
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.
Target cost control of construction projects is an important part of project management, and it plays a crucial role on the benefit of construction projects. In this paper, the issue about target cost control on the e...
详细信息
ISBN:
(纸本)9781424436705
Target cost control of construction projects is an important part of project management, and it plays a crucial role on the benefit of construction projects. In this paper, the issue about target cost control on the early stage of construction projects has been explored further. Firstly, this paper elaborates on determination principles and measurement methods of target cost of construction projects. Secondly, through the establishment of target cost programming model of construction projects and the use of simplex method on the linear programming, the established target cost programming model has been solved and the satisfied value of target cost control of construction projects has been determined based on final solution of the model. Finally, the application of method has been verified in practice. the purpose on target cost control of construction project has been achieved qualitatively and quantitatively. the effective control about target cost of construction projects on the early stage has been ensured.
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.
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.
暂无评论