Deviation is a recent constraint to balance a set of variables with respect to a given mean. We show that the propagators recently introduced are not bound-consistent when the mean is rational. We introduce bound-cons...
详细信息
ISBN:
(纸本)9783540749691
Deviation is a recent constraint to balance a set of variables with respect to a given mean. We show that the propagators recently introduced are not bound-consistent when the mean is rational. We introduce bound-consistent propagators running in linear time with respect to the number of variables. We evaluate the improvement in terms of efficiency and pruning obtained withthe new propagators on the Balanced Academic Curriculum Problem.
When implementing a propagator for a constraint, one must decide about variants: When implementing min, should one also implement max? Should one implement linear equations both with and without coefficients? Constrai...
详细信息
ISBN:
(纸本)9783540859574
When implementing a propagator for a constraint, one must decide about variants: When implementing min, should one also implement max? Should one implement linear equations both with and without coefficients? constraint variants are ubiquitous: implementing them requires considerable effort but yields better performance. this paper shows how to use variable views to derive perfect propagator variants: derived propagators inherit essential properties such as correctness and domain and bounds completeness.
the availability of commodity multi-core and multi-processor machines and the inherent parallelism in constraintprogramming search offer significant opportunities for constraintprogramming. they also present a funda...
详细信息
ISBN:
(纸本)9783540749691
the availability of commodity multi-core and multi-processor machines and the inherent parallelism in constraintprogramming search offer significant opportunities for constraintprogramming. they also present a fundamental challenge: how to exploit parallelism transparently to speed up constraint programs. this paper shows how to parallelize constraint programs transparently without changes to the code. the main technical idea consists of automatically lifting a sequential exploration strategy into its parallel counterpart, allowing workers to share and steal subproblems. Experimental results show that the parallel implementation may produces significant speedups on multi-core machines.
While the efficiency and scalability of modern SARI technology offers an intriguing alternative approach to constraint Solving via translation to SAT, previous work has mostly focused of the translation of specific ty...
详细信息
ISBN:
(纸本)9783540859574
While the efficiency and scalability of modern SARI technology offers an intriguing alternative approach to constraint Solving via translation to SAT, previous work has mostly focused of the translation of specific types of constraints, such as pseudo Boolean constraints;finite integer linear constraints, and constraints given as explicit listings of allowed triples. BY contrast, we present a translation of constraint models to SAT at language level, using the recently proposed constraint modeling language MiniZine, such that any satisfaction or optimization problem written in the language (not involving floats) can be automatically Booleanized and solved by one or more calls to a SAT solver. We discuss the strengths and weaknesses of such a universal constraint solver, Mid report oil a large-scale empirical evaluation of it against two existing solvers for MiniZinc: the finite domain solver distributed with MiniZinc and one based on the Gecode constraint;programming platform. our results indicate that, Booleanization indeed offers a competitive alternative, exhibiting superior performance on some classes of problems involving large numbers of constraints and complex integer arithmetic, ill addition to, naturally, problems dial arc already largely Boolean.
We present new results in crossword composition, showing that our program significantly outperforms previous successful techniques in the literature. We emphasize phase transition phenomena, and identify classes of ha...
详细信息
ISBN:
(纸本)9783540859574
We present new results in crossword composition, showing that our program significantly outperforms previous successful techniques in the literature. We emphasize phase transition phenomena, and identify classes of hard problems. Phase transition is shown to occur when varying problem parameters, such as the dictionary size and the number of blocked cells on a grid, of large-size realistic problems.
Many existing global constraints can be encoded as a conjunction of among constraints. An among constraint holds if the number of the variables in its scope whose value belongs to a prespecified set, which we call its...
详细信息
ISBN:
(纸本)9783319661582;9783319661575
Many existing global constraints can be encoded as a conjunction of among constraints. An among constraint holds if the number of the variables in its scope whose value belongs to a prespecified set, which we call its range, is within some given bounds. It is known that domain filtering algorithms can benefit from reasoning about the interaction of among constraints so that values can be filtered out taking into consideration several among constraints simultaneously. the present paper embarks into a systematic investigation on the circumstances under which it is possible to obtain efficient and complete domain filtering algorithms for conjunctions of among constraints. We start by observing that restrictions on boththe scope and the range of the among constraints are necessary to obtain meaningful results. then, we derive a domain flow-based filtering algorithm and present several applications. In particular, it is shown that the algorithm unifies and generalizes several previous existing results.
this paper introduces propagator groups as an abstraction for controlling the execution of propagators as implementations of constraints. Propagator groups enable users of a constraintprogramming system to program ho...
详细信息
ISBN:
(纸本)9783642042430
this paper introduces propagator groups as an abstraction for controlling the execution of propagators as implementations of constraints. Propagator groups enable users of a constraintprogramming system to program how propagators within a group are executed. the paper exemplifies propagator groups for controlling both propagation order and propagator interaction. Controlling propagation order is applied to debugging constraint propagation and optimal constraint propagation for Berge-acyclic propagator graphs. Controlling propagator interaction by encapsulating failure and entailment is applied to general reification and constructive disjunction. the paper describes an implementation of propagator groups (based on Gecode) that is applicable to any propagator-centered constraintprogramming system. Experiments show that groups incur little to no overhead and that the applications of groups axe practically usable and efficient.
A conceptual clustering is a set of formal concepts (i.e., closed itemsets) that defines a partition of a set of transactions. Finding a conceptual clustering is an NP-complete problem for which constraintprogramming...
详细信息
ISBN:
(纸本)9783319661582;9783319661575
A conceptual clustering is a set of formal concepts (i.e., closed itemsets) that defines a partition of a set of transactions. Finding a conceptual clustering is an NP-complete problem for which constraintprogramming (CP) and Integer Linear programming (ILP) approaches have been recently proposed. We introduce new CP models to solve this problem: a pure CP model that uses set constraints, and an hybrid model that uses a data mining tool to extract formal concepts in a preprocessing step and then uses CP to select a subset of formal concepts that defines a partition. We compare our new models with recent CP and ILP approaches on classical machine learning instances. We also introduce a new set of instances coming from a real application case, which aims at extracting setting concepts from an Enterprise Resource Planning (ERP) software. We consider two classic criteria to optimize, i.e., the frequency and the size. We show that these criteria lead to extreme solutions with either very few small formal concepts or many large formal concepts, and that compromise clusterings may be obtained by computing the Pareto front of non dominated clusterings.
Controlling an autonomous camera in three-dimensional (3D) virtual environments is a difficult task which manifests itself in many interactive computer graphics applications. Computer games [2] and guided exploration ...
ISBN:
(纸本)3540232419
Controlling an autonomous camera in three-dimensional (3D) virtual environments is a difficult task which manifests itself in many interactive computer graphics applications. Computer games [2] and guided exploration [1] are examples where autonomous cameras are required to provide suitable views of the scene as the user interacts withthe environment. the camera system is expected to consistently provide a suitable view of the target object(s) for the user. the camera control problem is often over-constrained. We successfully applied local search strategies to generate solutions to the problem in real-time. A cost is associated with each constraint (current constraints are: distance, height, occlusion, frame coherence rotation, and frame coherence distance), making some constraints more likely to be satisfied than others. A 3D game engine was developed to evaluate the cameras real-time performance. Preliminary comparisons with related works indicate significant performance benefits from the use of local search.
We revisit the Interactive CSP framework (ICSP) and propose a, new: somewhat more general model, which we call Cost-Driven Interactive CSP (CICSP). First, we extend the value acquisition by a more general concept of c...
详细信息
ISBN:
(纸本)9783642042430
We revisit the Interactive CSP framework (ICSP) and propose a, new: somewhat more general model, which we call Cost-Driven Interactive CSP (CICSP). First, we extend the value acquisition by a more general concept of constraint relaxation. Second, we loosen the basic assumption of ICSP that "value acquisition is expensive" by introducing external cost functions of the constraint relaxation and the constraint propagation effort. We also propose a general INTERACTIVE RELAXATION algorithm template that. is designated for CICSP. the effectiveness of this approach is illustrated oil a real-life scenario from the Functional Test Generation problem domain.
暂无评论