In this paper we propose off-line and on-line extensions to the Resource Constrained Project Scheduling Problem. the off-line extension is a variant of RCPSP with time lags and uncertain, bounded activity durations. I...
详细信息
ISBN:
(纸本)9783642153952
In this paper we propose off-line and on-line extensions to the Resource Constrained Project Scheduling Problem. the off-line extension is a variant of RCPSP with time lags and uncertain, bounded activity durations. In this context we improve over our previous work presented in [12] by proposing an incremental flow computation for finding minimal conflict sets and a set of filtering rules for cumulative constraint propagation. the on-line extension is based instead on considering an on-line semantics such as the Self-Timed Execution and take it into account in the scheduling process. Adding the on-line aspect to the problem makes the CSP framework no longer suitable. We have extended the CSP framework to take into account general search decisions and auxiliary unbound variables. An extensive set of experimental results show an improvement
A new interval constraint propagation algorithm;called MOnotonic Hall Consistency (Mohc), has recently been proposed. Mohc exploits monotonicity of functions to better filter variable domains. Embedded in an interval-...
详细信息
ISBN:
(纸本)9783642153952
A new interval constraint propagation algorithm;called MOnotonic Hall Consistency (Mohc), has recently been proposed. Mohc exploits monotonicity of functions to better filter variable domains. Embedded in an interval-based solver, Mohc shows very high performance for solving systems of numerical constraints (equations or inequalities) over the reals. However, the main drawback is that its revise procedure depends on two user-defined parameters. this paper reports a rigourous empirical study resulting in a variant of Mohc that avoids a manual tuning of the parameters. In particular, we propose a policy to adjust in an auto-adaptive way;during the search, the parameter sensitive to the monotonicity of the revised function.
In this paper we describe the design and implementation of CP-VIZ, a generic visualization platform for constraintprogramming. It provides multiple views to show the search tree, and the state of constraints and vari...
详细信息
ISBN:
(纸本)9783642153952
In this paper we describe the design and implementation of CP-VIZ, a generic visualization platform for constraintprogramming. It provides multiple views to show the search tree, and the state of constraints and variables for a postmortem analysis of a constraint program. Different to most previous visualization tools, it is system independent, using a light-weight, intermediate XML format to exchange information between solvers and the visualization tools. CP-VIZ is available under an open-source licence, and has already been interfaced to four different constraint systems.
Personalisation and context-awareness are fundamental concerns in Telephony. this paper introduces a rule-based system - 4CRULES - which enables context-sensitive call control by the means of feature configuration rul...
详细信息
ISBN:
(纸本)9783642153952
Personalisation and context-awareness are fundamental concerns in Telephony. this paper introduces a rule-based system - 4CRULES - which enables context-sensitive call control by the means of feature configuration rules. 4CRULES is interoperable with standard context services and compositional feature architectures. It has been designed to resolve feature interactions, manage conflicting preferences, and mitigate the uncertainty affecting context data. this is achieved through a constraint optimisation model that maximises adherence to user requirements and domain constraints. Experiments on a suite of instances confirm the practicality of the approach and highlight performance- and adherence-critical factors.
Scaling frequency and voltage in a coordinated manner is a promising way to reduce energy and power. we explore the use of dynamic frequency clocking within the datapath and datapath scheduling algorithms that can be ...
详细信息
the propositional satisfiability problem (SAT) is one of the simplest instances of constraintprogramming (CP): variables are bi-valued (can only take values 0 or 1), and all constraints are clauses (disjunctions of l...
详细信息
We introduce a parallelized version of tree-decomposition based dynamic programming for solving difficult weighted CSP instances on many cores. A tree decomposition organizes cost functions in a tree of collection of ...
详细信息
ISBN:
(纸本)9783642153952
We introduce a parallelized version of tree-decomposition based dynamic programming for solving difficult weighted CSP instances on many cores. A tree decomposition organizes cost functions in a tree of collection of functions called clusters. By processing the tree from the leaves up to the root, we solve each cluster concurrently, for each assignment of its separator, using a state-of-the-art exact sequential algorithm. the grain of parallelism obtained in tins way is directly related to the tree decomposition used. We use a dedicated strategy for building suitable decompositions. We present preliminary results of our prototype running on a cluster with hundreds of cores on different decomposable real problems. this implementation allowed us to solve the last open CELAR radio link frequency assignment instance to optimality.
this paper studies how to verify the conformity of a program with its specification and proposes a novel constraint-programming framework for bounded program verification (CPBPV). the CPBPV framework uses constraint s...
详细信息
this paper studies how to verify the conformity of a program with its specification and proposes a novel constraint-programming framework for bounded program verification (CPBPV). the CPBPV framework uses constraint stores to represent boththe specification and the program and explores execution paths of bounded length nondeterministically. the CPBPV framework detects non-conformities and provides counter examples when a path of bounded lengththat refutes some properties exists. the input program is partially correct under the boundness restrictions, if each constraint store so produced implies the post-condition. CPBPV does not explore spurious execution paths, as it incrementally prunes execution paths early by detecting that the constraint store is not consistent. CPBPV uses the rich language of constraintprogramming to express the constraint store. Finally, CPBPV is parameterized with a list of solvers which are tried in sequence, starting withthe least expensive and less general. Experimental results often produce orders of magnitude improvements over earlier approaches, running times being often independent of the size of the variable domains. Moreover, CPBPV was able to detect subtle errors in some programs for which other frameworks based on bounded model checking have failed.
In this paper we show that the power of using k-consistency techniques in a constraint problem is precisely captured by using a particular inference rule, which we call positive-hyper-resolution, on the direct Boolean...
详细信息
ISBN:
(纸本)9783642153952
In this paper we show that the power of using k-consistency techniques in a constraint problem is precisely captured by using a particular inference rule, which we call positive-hyper-resolution, on the direct Boolean encoding of the CSP instance. We also show that current clause-learning SAT-solvers will deduce any positive-hyper-resolvent of a fixed size from a given set of clauses in polynomial expected time. We combine these two results to show that, without being explicitly designed to do so, current clause-learning SAT-solvers efficiently simulate k-consistency techniques, for all values of k. We then give some experimental results to show that this feature allows clause-learning SAT-solvers to efficiently solve certain families of CSP instances which are challenging for conventional CP solvers.
this paper presents a novel domain-consistency algorithm which does not maintain supports dynamically during propagation, but rather maintain forbidden values. It introduces the optimal NAC4 (negative AC4) algorithm b...
详细信息
ISBN:
(纸本)9783642153952
this paper presents a novel domain-consistency algorithm which does not maintain supports dynamically during propagation, but rather maintain forbidden values. It introduces the optimal NAC4 (negative AC4) algorithm based on this idea. It further shows that maintaining forbidden values dynamically allows the generic algorithm AC5 to achieve domain consistency in time O(ed) for classes of constraints in which the number of supports is O(d(2)) but the number of forbidden values is O(d). the paper also shows how forbidden values and supports can be used jointly to achieve domain consistency on logical combinations of constraints and to compute validity as well as entailment of constraints. Experimental results show the benefits of the joint exploitation of supports and forbidden values.
暂无评论