While incremental propagation for global constraints is recognized to be important, little research has been devoted to how propagator-centered constraintprogramming systems should support incremental propagation. th...
详细信息
ISBN:
(纸本)9783540749691
While incremental propagation for global constraints is recognized to be important, little research has been devoted to how propagator-centered constraintprogramming systems should support incremental propagation. this paper introduces advisors as a simple and efficient, yet widely applicable method for supporting incremental propagation in a propagator-centered setting. the paper presents how advisors can be used for achieving different forms of incrementality and evaluates cost and benefit for several global constraints.
Recently, constraint-programming techniques have been used to generate test data and to verify the conformity of a program with its specification. constraint generated for these tasks may involve integer ranging on al...
详细信息
ISBN:
(纸本)9783540749691
Recently, constraint-programming techniques have been used to generate test data and to verify the conformity of a program with its specification. constraint generated for these tasks may involve integer ranging on all machine-integers, thus, the constraint-based modeling of the program and its specification is a critical issue. In this paper we investigate different models. We show that a straightforward translation of a program and its specification in a system of guarded constraints is ineffective. We outline the key role of Boolean abstractions and explore different search strategies on standard benchmarks.
the eplex library of the (ECLPSe)-P-i constraint Logic programming platform allows the integration of Mathematical programming techniques with its native constraint Logic programming techniques within the same unified...
详细信息
ISBN:
(纸本)3540292381
the eplex library of the (ECLPSe)-P-i constraint Logic programming platform allows the integration of Mathematical programming techniques with its native constraint Logic programming techniques within the same unified framework. It provides an interface to state-of-the-art Mathematical programming solvers, and a set of programming primitives that allow 'hybrid' techniques to be easily expressed. this paper presents these facilities, and discusses some associated implementation issues.
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.
In recent years, many constraint-specific filtering algorithms have been introduced. Such algorithms use the semantics of the constraint to perform filtering more efficiently than a generic algorithm. the usefulness o...
详细信息
Dual Consistency (DC) is a property of constraint Networks (CNs) which is equivalent, in its unrestricted form, to Path Consistency (PC). the principle is to perform successive singleton checks (i.e. enforcing arc con...
详细信息
ISBN:
(纸本)9783540749691
Dual Consistency (DC) is a property of constraint Networks (CNs) which is equivalent, in its unrestricted form, to Path Consistency (PC). the principle is to perform successive singleton checks (i.e. enforcing arc consistency after the assignment of a value to a variable) in order to identify inconsistent pairs of values, until a fixpoint is reached. In this paper, we propose two new algorithms, denoted by sDC2 and sDC3, to enforce (strong) PC following the DC approach. these algorithms can be seen as refinements of Mac Gregor's algorithm as they partially and totally exploit the incrementality of the underlying Arc Consistency algorithm. While sDC3 admits the same interesting worst-case complexities as PC8, sDC2 appears to be the most robust algorithm in practice. Indeed, compared to PC8 and the optimal PC2001, sDC2 is usually around one order of magnitude faster on large instances.
Although the Steel Mill Slab problem (prob 38 of CSPLib) has already been studied by the cp community, this approach is unfortunately not used anymore by steel producers since last century. Continuous casting is prefe...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
Although the Steel Mill Slab problem (prob 38 of CSPLib) has already been studied by the cp community, this approach is unfortunately not used anymore by steel producers since last century. Continuous casting is preferred instead, allowing higher throughput and better steel quality. this paper presents a cp model related to scheduling of operations for steel making with continuous casting. Activities considered range from the extraction of iron in the furnace to its casting in continuous casters. We describe the problem, detail a cp scheduling model that is finally used to solve real-life instances of some of the PSI Metals' customers.
We present the w constraint combinator that models while loops in constraintprogramming. Embedded in a finite domain constraint solver, it allows programmers to develop non-trivial arithmetical relations using loops,...
详细信息
ISBN:
(纸本)9783540749691
We present the w constraint combinator that models while loops in constraintprogramming. Embedded in a finite domain constraint solver, it allows programmers to develop non-trivial arithmetical relations using loops, exactly as in an imperative language style. the deduction capabilities of this combinator come from abstract interpretation over the polyhedra abstract domain. this combinator has already demonstrated its utility in constraint- based verification and we argue that it also facilitates the rapid prototyping of arithmetic constraints (e.g. power, gcd or sum).
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.
We investigate soft open constraints. We generalize and unify classes of soft constraints and adapt them to the open setting. We give sufficient Conditions for generalized classes of decomposition-based and edit-based...
详细信息
ISBN:
(纸本)9783642042430
We investigate soft open constraints. We generalize and unify classes of soft constraints and adapt them to the open setting. We give sufficient Conditions for generalized classes of decomposition-based and edit-based soft constraints to be contractible. Finally, we outline a propagator for an open generalized edit-based Soft REGULAR constraint.
暂无评论