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
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.
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.
the automatic tuning of the parameters of algorithms and automatic selection of algorithms has received a lot of attention recently. One possible approach is the use of machine learning techniques to learn classifiers...
详细信息
ISBN:
(纸本)9783642153952
the automatic tuning of the parameters of algorithms and automatic selection of algorithms has received a lot of attention recently. One possible approach is the use of machine learning techniques to learn classifiers which, given the characteristics of a particular problem, make a decision as to which algorithm or what parameters to use. Little research has been done into which machine learning algorithms are suitable and the impact of picking the "right" over the "wrong" technique. this paper investigates the differences in performance of several techniques on different data sets. it furthermore provides evidence that by using a meta-technique which combines several machine learning algorithms, we can avoid the problem of having to pick the "best" one and still achieve good performance.
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.
Forbidden patterns problems are a generalisation of (finite) constraint satisfaction problems which are definable in Feder and Vardi9;s logic MMSNP [1]. in fact, they are examples of infinite constraint satisfactio...
详细信息
ISBN:
(纸本)9783642153952
Forbidden patterns problems are a generalisation of (finite) constraint satisfaction problems which are definable in Feder and Vardi's logic MMSNP [1]. in fact, they are examples of infinite constraint satisfaction problems with nice model theoretic properties introduced by Bodirsky [2]. In previous work [3], we introduced a normal form for these forbidden patterns problems which allowed us to provide an effective characterisation of when a problem is a finite or infinite constraint satisfaction problem. One of the central concepts of this normal form is that of a recolouring. In the presence of a recolouring from a forbidden patterns problem Omega(1) to another forbidden patterns problem Omega(2), containment of Omega(1) in Omega(2) follows. the converse does not hold in general and it remained open whether it did in the case of problems being given in our normal form. In this paper, we prove that this is indeed the case. We also show that the recolouring problem is Pi(p)(2)-harpd and in Sigma(p)(3).
暂无评论