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.
An important class of CSP heuristics work by sampling information during search in order to inform subsequent decisions. An example is the use of failures, in the form of constraint weights, to guide variable selectio...
详细信息
ISBN:
(纸本)9783540749691
An important class of CSP heuristics work by sampling information during search in order to inform subsequent decisions. An example is the use of failures, in the form of constraint weights, to guide variable selection in a weighted degree procedure. the present research analyses the characteristics of the sampling process in this procedure and the manner in which information is used, in order to better understand this type of strategy and to discover further enhancements.
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...
详细信息
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.
Bounded Max-Sum is a message-passing algorithm for solving Distributed constraint Optimization Problems (DCOP) able to compute solutions with a guaranteed approximation ratio. In this paper we show that the introducti...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
Bounded Max-Sum is a message-passing algorithm for solving Distributed constraint Optimization Problems (DCOP) able to compute solutions with a guaranteed approximation ratio. In this paper we show that the introduction of an intermediate step that decomposes functions may significantly improve its accuracy. this is especially relevant in critical applications (e. g. automatic surveillance, disaster response scenarios) where the accuracy of solutions is of vital importance.
暂无评论