this paper introduces a new filtering algorithm for handling systems of quadratic equations and inequations. Such constraints are widely used to model distance relations in numerous application areas ranging from robo...
详细信息
In recent years, there has been much research on local search techniques for solving constraint satisfaction problems, including Boolean satisfiability problems. Some of the most successful procedures combine a form o...
详细信息
作者：
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 Erwig'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.
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.
We identify an important class of symmetries in constraintprogramming, arising from matrices of decision variables where rows and columns can be swapped. Whilst lexicographically ordering the rows(columns) breaks all...
详细信息
In this paper we study the complexity of the weighted maximum constraint satisfaction problem (MAX CSP) over an arbitrary finite domain. In this problem, one is given a collection of weighted constraints on overlappin...
详细信息
ISBN:
(纸本)3540292381
In this paper we study the complexity of the weighted maximum constraint satisfaction problem (MAX CSP) over an arbitrary finite domain. In this problem, one is given a collection of weighted constraints on overlapping sets of variables, and the goal is to find an assignment of values to the variables so as to maximize the total weight of satisfied constraints. MAX CSP is NP-hard in general;however, some restrictions on the form of constraints may ensure tractability. Recent results indicate that there is a connection between tractability of such restricted problems and supermodularity of the allowed constraint types with respect to some lattice ordering of the domain. We prove several results confirming this in a special case when the lattice ordering is as loose as possible, i.e., a diamond one.
Model-based applications in engineering, such as diagnosis,configuration or interactive decision-support systems, require embedded constraint solvers with challenging capabilities. Not only consistency checking and so...
详细信息
暂无评论