constraint propagation is widely recognized as a fundamental reasoning component in constraintprogramming. In the last decade, the concept of "global constraint" has attracted significant attention, since i...
详细信息
ISBN:
(纸本)3540202021
constraint propagation is widely recognized as a fundamental reasoning component in constraintprogramming. In the last decade, the concept of "global constraint" has attracted significant attention, since it is critical to achieve reasonable pruning, and efficiency, in many applications. However, even if the name "global constraint" carries a strong intuition in itself, there is no formal definition of this important concept. this paper proposes various notions of globality in order to understand this concept more thoroughly.
constraint models contain a number of common patterns. For example, many constraint models involve an array of decision variables with symmetric rows and/or columns. By documenting such constraint patterns, we can sha...
详细信息
ISBN:
(纸本)3540202021
constraint models contain a number of common patterns. For example, many constraint models involve an array of decision variables with symmetric rows and/or columns. By documenting such constraint patterns, we can share modelling expertise. constraint solvers can also be extended to exploit such patterns. For example, we can develop specialized methods like the global lexicographical ordering constraint for breaking such row and column symmetry.
One strand of CP research seeks to design a small set of primitives and operators that can be used to build an appropriate algorithm for solving any given combinatorial problem. the aim is to "package" CP, s...
详细信息
ISBN:
(纸本)3540202021
One strand of CP research seeks to design a small set of primitives and operators that can be used to build an appropriate algorithm for solving any given combinatorial problem. the aim is to "package" CP, simplifying its use, in contrast to current systems which offer application developers a full constraintprogramming language. In this talk we examine the risks of this line of research, and argue that our field is still too immature to be ready for "packaging".
作者：
Golden, KPang, WLNASA
Ames Res Ctr Computat Sci Div Moffett Field CA 94035 USA NASA
Ames Res Ctr QSS Grp Inc Moffett Field CA 94035 USA
this paper discusses an approach to representing and reasoning about constraints over strings. We discuss how string domains can often be concisely represented using regular languages, and how constraints over strings...
详细信息
ISBN:
(纸本)3540202021
this paper discusses an approach to representing and reasoning about constraints over strings. We discuss how string domains can often be concisely represented using regular languages, and how constraints over strings, and domain operations on sets of strings, can be carried out using this representation.
In constraint solving for finite domains, efficient set representation is an important issue. In this paper we propose an enhancement of Erwig9;s diet representation called the enhanced diet, which represents a fin...
详细信息
ISBN:
(纸本)3540202021
In constraint solving for finite domains, efficient set representation is an important issue. In this paper we propose an enhancement of Erwig's diet representation called the enhanced diet, which represents a finite domain as an AVL tree of intervals. In addition to element insertion and deletion, we show that the domain splitting used for constraints such as X less than or equal to Y can be done in O(log m) steps by adopting Crane's Algorithm, where m is the number of intervals, not the number of elements.
Local search algorithms have been very successful for solving constraint satisfaction problems (CSP). However, a major weakness has been that local search is unable to detect unsolvability and is thus not suitable for...
详细信息
ISBN:
(纸本)3540202021
Local search algorithms have been very successful for solving constraint satisfaction problems (CSP). However, a major weakness has been that local search is unable to detect unsolvability and is thus not suitable for highly constrained or overconstrained problems. In this paper, we present a scheme where a local search algorithm, the break-out algorithm, is used to identify hard or unsolvable subproblems and to derive a variable ordering that places the hardest subproblems first.
We study a generalization of the constraint satisfaction problem (CSP), the periodic constraint satisfaction problem. An input instance of the periodic CSP is a finite set of "generating" constraints over a ...
详细信息
ISBN:
(纸本)3540202021
We study a generalization of the constraint satisfaction problem (CSP), the periodic constraint satisfaction problem. An input instance of the periodic CSP is a finite set of "generating" constraints over a structured variable set that implicitly specifies a larger, possibly infinite set of constraints;the problem is to decide whether or not the larger set of constraints has a satisfying assignment. this model is natural for studying constraint networks consisting of constraints obeying a high degree of regularity or symmetry. Our main contribution is the identification of two broad polynomial-time tractable subclasses of the periodic CSP.
Multiple sequence alignment is a central problem in Bioinformatics. A known integer programming approach is to apply branch-and-cut to exponentially large graph-theoretic models. this paper describes a new integer pro...
详细信息
ISBN:
(纸本)3540202021
Multiple sequence alignment is a central problem in Bioinformatics. A known integer programming approach is to apply branch-and-cut to exponentially large graph-theoretic models. this paper describes a new integer program formulation that generates models small enough to be passed to generic solvers. the formulation is a hybrid relating the sparse alignment graph with a compact encoding of the alignment matrix via channelling constraints. Alignments obtained with a SAT-based local search algorithm are competitive withthose of state-of-the-art algorithms, though execution times are much longer.
暂无评论