By introducing the Regular Membership constraint, Gilles Pesant pioneered the idea of basing constraints on formal languages. the paper presented here is highly motivated by this work, taking the obvious next step, na...
详细信息
ISBN:
(纸本)3540462678
By introducing the Regular Membership constraint, Gilles Pesant pioneered the idea of basing constraints on formal languages. the paper presented here is highly motivated by this work, taking the obvious next step, namely to investigate constraints based on grammars higher up in the Chomsky hierarchy. We devise an arc-consistency algorithm for context-free grammars, investigate when logic combinations of grammar constraints are tractable, show how to exploit non-constant size grammars and reorderings of languages, and study where the boundaries run between regular, context-free, and context-sensitive grammar filtering.
We present an incomplete filtering algorithm for the circuit constraint. the filter removes redundant values by eliminating nonhamiltonian edges from the associated graph. We identify nonhamiltonian edges by analyzing...
详细信息
ISBN:
(纸本)3540462678
We present an incomplete filtering algorithm for the circuit constraint. the filter removes redundant values by eliminating nonhamiltonian edges from the associated graph. We identify nonhamiltonian edges by analyzing a smaller graph with labeled edges that is defined on a separator of the original graph. the complexity of the procedure for each separator S is approximately O(vertical bar S vertical bar(5)). We found that it identified all infeasible instances and eliminated about one-third of the redundant domain elements in feasible instances.
tIn this paper we give an overview of applications of constraintprogramming for IP (Internet Protocol) data networks, and discuss the problem of Resilience Analysis in more detail. In this problem we try to predict t...
详细信息
ISBN:
(纸本)3540462678
tIn this paper we give an overview of applications of constraintprogramming for IP (Internet Protocol) data networks, and discuss the problem of Resilience Analysis in more detail. In this problem we try to predict the loading of a network in different failure scenarios, without knowing end-to-end flow values throughout the network;the inference is based only on observed link traffic values. the related problem of Traffic Flow Analysis aims to derive a traffic matrix from the observed link traffic data. this is a severely under-constrained problem, we can show that the obtained flow values vary widely in different, feasible solutions. Experimental results indicate that using the same data much more accurate, bounded results can be obtained for Resilience Analysis.
In this paper we show that the clique concept can be exploited in order to solve Max-CSP. We present a clique inference process which leads to construct linear systems useful for computing new lower bounds. the clique...
详细信息
ISBN:
(纸本)3540462678
In this paper we show that the clique concept can be exploited in order to solve Max-CSP. We present a clique inference process which leads to construct linear systems useful for computing new lower bounds. the clique inference process is introduced in the PFC-MPRDAC [5] algorithm and the obtained algorithm is called PFC-MPRDAC+CBB (CBB for Clique Based Bound). the carried out experiments have shown that PFC-MPRDAC+CBB leads to obtain very encouraging results.
Since electromagnetic waves are strongly attenuated inside the water, the satellite based global positioning system (cpS) cannot be used by submarine robots except at the surface of the water. this paper shows that th...
详细信息
ISBN:
(纸本)3540462678
Since electromagnetic waves are strongly attenuated inside the water, the satellite based global positioning system (cpS) cannot be used by submarine robots except at the surface of the water. this paper shows that the localization problem in deep water can often be cast into a continuous constraints satisfaction problem where interval constraints propagation algorithms are particularly efficient. the efficiency of the resulting propagation methods is illustrated on the localization of a submarine robot, named Redermor. the experiments have been collected by the GESMA (Groupe d'Etude Sous-Marine de l'Atlantique) in the Douarnenez bay, in Brittany.
Symmetries are one of the difficulties constraintprogramming users have to deal with. One way to get rid of symmetries is to add lex constraints. However, it can adversely affect the efficiency of a tree search metho...
详细信息
ISBN:
(纸本)3540462678
Symmetries are one of the difficulties constraintprogramming users have to deal with. One way to get rid of symmetries is to add lex constraints. However, it can adversely affect the efficiency of a tree search method if the lex constraints remove the solution that would have been found at the first place. We propose to use an alternative filtering algorithm which does not exclude the first solution. We present both a theoretical analysis and some experimental evidence that it is as efficient as lex constraints. We also show that its efficiency does not depend much on the variable ordering used in the tree search. Last, we show that it can prune more nodes than the SBDS method.
Tractability results for structural subproblems have generally been considered for explicit relations listing the allowed assignments. In this paper we define a representation which allows us to express constraint rel...
详细信息
ISBN:
(纸本)3540462678
Tractability results for structural subproblems have generally been considered for explicit relations listing the allowed assignments. In this paper we define a representation which allows us to express constraint relations as either an explicit set of allowed labelings, or an explicit set of disallowed labelings, whichever is smaller. We demonstrate a new structural width parameter, which we call the interaction width, that when bounded allows us to carry over well known structural decompositions to this more concise representation. Our results naturally derive new structurally tractable classes for SAT.
thanks to its extended expressiveness, the quantified constraint satisfaction problem (QCSP) can be used to model problems that are difficult to express in the standard CSP formalism. this is only recently that the co...
详细信息
ISBN:
(纸本)3540462678
thanks to its extended expressiveness, the quantified constraint satisfaction problem (QCSP) can be used to model problems that are difficult to express in the standard CSP formalism. this is only recently that the constraint community got interested in QCSP and proposed algorithms to solve it. In this paper we propose BlockSolve, an algorithm for solving QCSPs that factorizes computations made in branches of the search tree. Instead of following the order of the variables in the quantification sequence, our technique searches for combinations of values for existential variables at the bottom of the tree that will work for (several) values of universal variables earlier in the sequence. An experimental study shows the good performance of BlockSolve compared to a state of the art QCSP solver.
We introduce the SomeDifferent constraint as a generalization of AllDifferent. SomeDifferent requires that values assigned to some pairs of variables will be different. It has many practical applications. For example,...
详细信息
ISBN:
(纸本)3540462678
We introduce the SomeDifferent constraint as a generalization of AllDifferent. SomeDifferent requires that values assigned to some pairs of variables will be different. It has many practical applications. For example, in workforce management, it may enforce the requirement that the same worker is not assigned to two jobs which are overlapping in time. Propagation of the constraint for hyper-arc consistency is NP hard. We present a propagation algorithm with worst case time complexity O(n(3)ss(n)) where n is the number of variables and ss approximate to 3.5 (ignoring a trivial dependence on the representation of the domains). We also elaborate on several heuristics which greatly reduce the algorithm's running time in practice. We provide experimental results, obtained on a real-world workforce management problem and on synthetic data, which demonstrate the feasibility of our approach.
the French nuclear park comprises 58 nuclear reactors distributed through the national territory on 19 geographical sites. they must be repeatedly stopped, for refueling and maintenance. the scheduling of these outage...
详细信息
ISBN:
(纸本)3540462678
the French nuclear park comprises 58 nuclear reactors distributed through the national territory on 19 geographical sites. they must be repeatedly stopped, for refueling and maintenance. the scheduling of these outages has to comply with various constraints, regarding safety, maintenance logistic, and plant operation, whilst it must contribute to the producer profit maximization. this industrial problem appears to be a hard combinatorial problem that conventional methods used up to now by Electricite de France (mainly based on Mixed Integer programming) fail to solve properly. We present in this paper a new approach for modeling and solving this problem, combining constraintprogramming (cp) and Local Search. cp is used to find solutions to the outage scheduling problem, while Local Search is used to improve solutions with respect to a heuristic cost criterion. It leads to find solutions as good as withthe conventional approaches, but taking into account all the constraints and in very reduced computing time.
暂无评论