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.
Random instances are widely used as benchmarks in evaluating algorithms for finite-domain constraint satisfaction problems (CSPs).We present an analysis that shows why deciding satisfiability of instances from some di...
详细信息
In this work, we extend the class of Horn constraints to include disjunctions with an arbitrary number of linear inequalities, linear disequations and non-linear disequations. We propose a preprocess step in which two...
详细信息
Real-world constraint problems abound with *** with incomplete or erroneous data are often simplified at present to tractable deterministic models, or modified using error correction methods, withthe aim of seeking a...
详细信息
A typical technique in integer programming for filtering variables is known as variable fixing. the optimal dual solution of the linear relaxation can be used to detect some of the 0/1 variables that must be fixed to ...
详细信息
ISBN:
(纸本)9783319661582;9783319661575
A typical technique in integer programming for filtering variables is known as variable fixing. the optimal dual solution of the linear relaxation can be used to detect some of the 0/1 variables that must be fixed to either 0 or 1 in any solution improving the best known, but this filtering is incomplete. A complete technique is proposed in this paper for satisfaction problems with an ideal integer programming formulation. We show, in this case, that the 0/1 variables taking the same value in all solutions can be identified by solving a single linear program with twice the number of the original variables. In other words, a complete variable fixing of the 0/1 variables can be performed for a small overhead. As a result, this technique can be used to design generic arc consistency algorithms. We believe it is particularly useful to quickly prototype arc consistency algorithms for numerous polynomial constraints and demonstrate it for the family of Sequence global constraints.
We study a global constraint, the "inter-distance constraint" that ensures that the distance between any pair of variables is at least equal to a given value. When this value is 1, the inter-distance constra...
详细信息
ISBN:
(纸本)3540292381
We study a global constraint, the "inter-distance constraint" that ensures that the distance between any pair of variables is at least equal to a given value. When this value is 1, the inter-distance constraint reduces to the all-different constraint. We introduce an algorithm to propagate this constraint and we show that, when domains of the variables are intervals, our algorithm achieves arc-B-consistency. It provides tighter bounds than generic scheduling constraint propagation algorithms (like edge-finding) that could be used to capture this constraint. the worst case complexity of the algorithm is cubic but it behaves well in practice and it drastically reduces the search space. Experiments on special Job-Shop problems and on an industrial problem are reported.
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".
Symmetries in constraint satisfaction problems (CSPs) areone of the difficulties that practitioners have to deal with. We present in this paper a new method based on the symmetries of decisions taken from the root of ...
详细信息
this paper presents a new cumulatives constraint, which generalizes the original cumulative constraint in different ways. the two most important aspects consist in permitting multiple cumulative resources as well as n...
详细信息
暂无评论