In this paper, we present a major improvement in the search procedures in constraintprogramming. First, we integrate various search procedures from Al and OR. Second, we parallelize the search on shared-memory comput...
详细信息
ISBN:
(纸本)3540666265
In this paper, we present a major improvement in the search procedures in constraintprogramming. First, we integrate various search procedures from Al and OR. Second, we parallelize the search on shared-memory computers. third, we add an object-oriented extensible control language to implement complex complete and incomplete search procedures. the result is a powerful set of tools which offers both brute force search using simple search procedures and parallelism, and finely tuned search procedures using that expressive control language. Withthis, we were able both to solve difficult and open problems using complete search procedures, and to quickly produce good results using incomplete search procedures.
in this paper, we propose a constraint-based approach to determining protein structures compatible with distance constraints obtained from Nuclear Magnetic Resonance (NMR) data. We compare the performance of our propo...
详细信息
ISBN:
(纸本)3540666265
in this paper, we propose a constraint-based approach to determining protein structures compatible with distance constraints obtained from Nuclear Magnetic Resonance (NMR) data. We compare the performance of our proposed algorithm with DYANA ("Dynamics algorithm for NMR applications" [1]) an existing commercial application based on simulated annealing. For our test case, computation time for DYANA was more than six hours, whereas the method we propose produced similar results in 8 minutes, so we show that the application of constraintprogramming (cp) technology can greatly reduce computation time. this is a major advantage because this NMR technique generally demands multiple runs of structural computation.
We introduce a new method for excluding symmetries in constraint based search. To our knowledge, it is the first declarative method that can be applied to arbitrary symmetries. Our method is based on the notion of sym...
详细信息
ISBN:
(纸本)3540666265
We introduce a new method for excluding symmetries in constraint based search. To our knowledge, it is the first declarative method that can be applied to arbitrary symmetries. Our method is based on the notion of symmetric constraints, which are used in our modification of a general constraint based search algorithm;the method does not influence the search strategy. Furthermore, it can be used with either the full set of symmetries, or with an subset of all symmetries. We proof correctness, completeness and symmetry exclusion properties of our method. We then show how to apply the method in the special case of geometric symmetries (rotations and reflections) and permutation symmetries. Furthermore, we give results from practical applications.
Most work on constraint satisfaction problems (CSP) starts with a standard problem definition and focuses on algorithms for finding solutions. However, formulating a CSP so that it can be solved by such methods is oft...
详细信息
ISBN:
(纸本)3540666265
Most work on constraint satisfaction problems (CSP) starts with a standard problem definition and focuses on algorithms for finding solutions. However, formulating a CSP so that it can be solved by such methods is often a difficult problem in itself. In this paper, we consider the problem of routing in networks, an important problem in communication networks. It is as an example of a problem where a CSP formulation would lead to unmanageable solution complexity. We show how an abstraction technique results in tractable formulations and makes the machinery of CSP applicable to this problem.
In this paper we compare the performance of three constraint weighting schemes with one of the latest and fastest WSAT heuristics: novelty. We extend previous results from satisfiability testing by looking at the broa...
详细信息
ISBN:
(纸本)3540666265
In this paper we compare the performance of three constraint weighting schemes with one of the latest and fastest WSAT heuristics: novelty. We extend previous results from satisfiability testing by looking at the broader domain of constraint satisfaction and test for differences in performance using randomly generated problems and problems based on realistic situations and assumptions. We find constraint weighting produces fairly consistent behaviour within problem domains, and is more influenced by the number and interconnectedness of constraints than the realism or randomness of a problem. We conclude that constraint weighting is better suited to smaller structured problems, where it is can clearly distinguish between different constraint groups.
Since the origins of the constraint satisfaction paradigm, its restriction to binary constraints has concentrated a significant part of the work. this is understandable because new ideas/techniques are usually much si...
详细信息
ISBN:
(纸本)3540666265
Since the origins of the constraint satisfaction paradigm, its restriction to binary constraints has concentrated a significant part of the work. this is understandable because new ideas/techniques are usually much simpler to present/elaborate by first restricting them to the binary case. (See for example the are consistency algorithms, such as AC-3 or AC-4, which have been presented first in their binary version [10, 12], before being extended to non-binary constraints [11, 13].) But this inclination has highly increased in the early nineties. Authors indeed justified this restriction by the fact that any non-binary constraint network can polyniomally be converted into an equivalent binary one [6,8,5,19]. And, in most cases, they never extended their work to non-binary constraints.
the studies of a frequency assignment problem (also called a channel assignment problem) in cellular mobile systems have a long history [4], and various AI techniques have been applied to this problem [1,3]. A frequen...
ISBN:
(纸本)3540666265
the studies of a frequency assignment problem (also called a channel assignment problem) in cellular mobile systems have a long history [4], and various AI techniques have been applied to this problem [1,3]. A frequency assignment problem is formalized as follows1. Frequencies are represented by positive integers 1,2,3, .... Given: • N: the number of cells • di,1 1 N: the number of requested calls (demands) in cell i • cij,1 i,j N:the frequency separation required between a call in cell i and a call in cell j
We define a model for heuristic tree search which assumes that the quality of the heuristic used for ordering the successors of a node improves as depth increases. We show that a usual value ordering heuristic for sol...
详细信息
ISBN:
(纸本)3540666265
We define a model for heuristic tree search which assumes that the quality of the heuristic used for ordering the successors of a node improves as depth increases. We show that a usual value ordering heuristic for solving constraint satisfaction problems fits to this model. Our model defines a partial order on the leaf nodes of the search tree, according to their probability to be a solution. We check which search strategies among interleaved depth-first search (IDFS), limited discrepancy search (LDS) and depth-bounded discrepancy search (DDS) visit the leaf nodes while respecting the partial order. Our study leads to conclude that, among these strategies, only Pure IDFS and a slight modification of improved LDS respect it.
Diagrammatic human-computer interfaces are now becoming standard. In the near future, diagrammatic front-ends, such as those of UML-based CASE tools, will be required to offer a much more intelligent behavior than jus...
详细信息
ISBN:
(纸本)3540666265
Diagrammatic human-computer interfaces are now becoming standard. In the near future, diagrammatic front-ends, such as those of UML-based CASE tools, will be required to offer a much more intelligent behavior than just editing. Yet there is very little formal support and there are almost no tools available for the construction of such environments. the present paper introduces a constraint-based formalism for the specification and implementation of complex diagrammatic environments. We start from grammar-based definitions of diagrammatic languages and show how a constraint solver for diagram recognition and interpretation can automatically be constructed from such grammars. In a second step, the capabilities of these solvers are extended by allowing to axiomatise formal diagrammatic systems, such as Venn Diagrams, so that they can be regarded as a new constraint domain. the ultimate aim of this schema is to establish a language of type CLP(Diagram) for diagrammatic reasoning applications.
the class of constraint satisfaction problems (CSPs) over finite domains has been shown to be NP-complete, but many tractable subclasses have been identified in the literature. In this paper we are interested in restr...
详细信息
ISBN:
(纸本)3540666265
the class of constraint satisfaction problems (CSPs) over finite domains has been shown to be NP-complete, but many tractable subclasses have been identified in the literature. In this paper we are interested in restrictions on the types of constraint relations in CSP instances. By a result of Jeavons et al. we know that a key to the complexity of classes arising from such restrictions is the closure properties of the sets of relations. It has been shown that sets of relations that are closed under constant, majority, affine, or associative, commutative, and idempotent (ACI) functions yield tractable subclasses of CSP. However, it has been unknown whether other closure properties may generate tractable subclasses. In this paper we introduce a class of tractable (in fact, SL-complete) CSPs based on bipartite graphs. We show that there are members of this class that are not closed under constant, majority, affine, or ACI functions, and that it, therefore, is incomparable with previously identified classes.
暂无评论