constraintprogramming is a family of techniques for solving combinatorial problems, where the problem is modelled as a set of decision variables (typically with finite domains) and a set of constraints that express r...
详细信息
constraintprogramming is a family of techniques for solving combinatorial problems, where the problem is modelled as a set of decision variables (typically with finite domains) and a set of constraints that express relations among the decision variables. One key concept in constraintprogramming is propagation: reasoning on a constraint or set of constraints to derive new facts, typically to remove values from the domains of decision variables. Specialized propagation algorithms (propagators) exist for many classes of constraints. the concept of support is pervasive in the design of propagators. Traditionally, when a domain value ceases to have support, it may be removed because it takes part in no solutions. Arc-consistency algorithms such as AC2001 [in: Proceedings 17thinternational Joint conference on Artificial Intelligence (IJCAI 2001), 2001, pp. 309-315] make use of support in the form of a single domain value. GAC algorithms such as GAC-Schema [in: Proceedings 15thinternational Joint conference on Artificial Intelligence (IJCAI 97), 1997, pp. 398-404] use a tuple of values to support each literal. We generalize these notions of support in two ways. First, we allow a set of tuples to act as support. Second, the supported object is generalized from a set of literals (GAC-Schema) to an entire constraint or any part of it. We design a methodology for developing correct propagators using generalized support. A constraint is expressed as a family of support properties, which may be proven correct against the formal semantics of the constraint. We show how to derive correct propagators from the constructive proofs of the support properties. the framework is carefully designed to allow efficient algorithms to be produced. Derived algorithms may make use of dynamic literal triggers or watched literals [in: Proc. 12thinternationalconference on the principles and practice of constraintprogramming (cp 2006), 2006, pp. 182-197] for efficiency. Finally, three case st
the tcc model is a formalism for reactive concurrent constraintprogramming. In this paper we propose a model of temporal concurrent constraintprogramming which adds to tcc the capability of modeling asynchronous and...
详细信息
Applying GAC on conjunctions of constraints can lead to more powerful pruning [1].We show that there exists a simple heuristic for deciding which constraints might be useful to conjoin. the result is a useful automati...
详细信息
In this paper we show, for the specific problem of test pattern optimisation, that adapting constraint propagation with results obtained from local search outperforms the use of each of these techniques alone. We show...
详细信息
作者：
Ringwelski, GeorgGMD FIRST
German National Research Center for Information Technology Kekuléstraße 7 Berlin12489 Germany
A constraint Satisfaction Problem (CSP) is to find an assignment to a set of variables that is consistent wrt. a set of constraints over these variables. CSPs frequentlyarise in applications of distributed artificial ...
ISBN:
(纸本)3540428631
A constraint Satisfaction Problem (CSP) is to find an assignment to a set of variables that is consistent wrt. a set of constraints over these variables. CSPs frequentlyarise in applications of distributed artificial intelligence [3] and may often not be solved bya centralized constraint solver for privacyor security reasons. In this distributed case (DCSP) constraints and variables are distributed among multiple automated agents.
We present Branch-and-Check, a hybrid framework integrating Mixed Integer programming and constraint Logic programming, which encapsulates the traditional Benders Decomposition and Branch-and-Bound as special cases. I...
详细信息
the modelling process of constraint satisfaction problems as constraint programs requires sophisticated reasoning skills and involves crucial decisions on which variable representations to choose, on which constraint ...
ISBN:
(纸本)3540428631
the modelling process of constraint satisfaction problems as constraint programs requires sophisticated reasoning skills and involves crucial decisions on which variable representations to choose, on which constraint formulation to state, and on which solution methods to employ. Furthermore, the tight interaction between representation, constraint formulation, and solution methods adds another degree of complexity to the modelling task. For instance, the choice of the constraint formulation is strongly affected by the choice of the representation of variables and values, and by the choice of the solution methods. In addition, the performance of solution methods is sensitive to the problem instances. thus, modelling combinatorial optimisation problems so as to solve them in more efficient ways is a major challenge for constraintprogramming.
the temporal ccp model tcc [3] is aimed at specifying timed systems. Time is conceptually divided into discrete intervals. In a particular time interval, a ccp process receives a stimulus (i.e. a constraint)from the e...
ISBN:
(纸本)3540428631
the temporal ccp model tcc [3] is aimed at specifying timed systems. Time is conceptually divided into discrete intervals. In a particular time interval, a ccp process receives a stimulus (i.e. a constraint)from the environment, it executes withthis stimulus as the initial store, and when it reaches its resting point, it responds to the environment withthe resulting store. Also the resting point determines a residual process, which is then executed in the next time interval. this temporal ccp model is inherently deterministic and synchronous.
constraint based techniques offer a promising approach to coordinating a set of agents in solving a distributed resource allocation problem. Distributed resource allocation is a general problem in which a set of agent...
ISBN:
(纸本)3540428631
constraint based techniques offer a promising approach to coordinating a set of agents in solving a distributed resource allocation problem. Distributed resource allocation is a general problem in which a set of agents must intelligently assign their resources to a set of tasks such that all tasks are performed with respect to certain criteria. this problem arises in many real-world domains such as distributed sensor networks [4], disaster rescue[2], hospital scheduling[1], and others.
We explore the problem of deriving explanations and implications for constraint satisfaction problems (CSPs). We show that consistency methods can be used to generate inferences that support both functions. Explanatio...
详细信息
暂无评论