the proceedings contain 41 papers. the special focus in this conference is on principles and practice of constraintprogramming. the topics include: the rough guide to constraint propagation;non-binary constraints;the...
ISBN:
(纸本)3540666265
the proceedings contain 41 papers. the special focus in this conference is on principles and practice of constraintprogramming. the topics include: the rough guide to constraint propagation;non-binary constraints;the theory of discrete lagrange multipliers for nonlinear discrete optimization;operational equivalence of CHR programs and constraints;automatic generation of constraint propagation algorithms for small finite domains;excluding symmetries in constraint based search;onforward checking for non-binary constraint satisfaction;enforcing arc consistency on global constraints by solving subCSPs on the fly;exploiting bipartiteness to identify yet another tractable subclass of CSP;towards a complete classification of tractability in point algebras for nonlinear time;a meta-heuristic factory for vehicle routing problems;closure functions and width 1 problems;cost-based domain filtering;resource allocation in networks using abstraction and constraint satisfaction techniques;optimal distributed arc-consistency;multistep filtering operators for ordinary differential equations and a framework for constraintprogramming based column generation.
Several constraint satisfaction algorithms focus on numeric constraint satisfaction problems (CSPs). A numeric CSP is defined by a set of variables, their domains, intervals in ?\Re, and the set of constraints, expres...
ISBN:
(纸本)3540666265
Several constraint satisfaction algorithms focus on numeric constraint satisfaction problems (CSPs). A numeric CSP is defined by a set of variables, their domains, intervals in ?\Re, and the set of constraints, expressed as mathematical relations, which must be satisfied for any solution. Such CSPs can model many engineering and design problems from domains such as mechanical, electrical and civil engineering.
Local Consistency has proven to be an important notion in the study of constraint satisfaction problems. We give an algebraic condition that characterizes all the constraint types for which generalized are-consistency...
详细信息
ISBN:
(纸本)3540666265
Local Consistency has proven to be an important notion in the study of constraint satisfaction problems. We give an algebraic condition that characterizes all the constraint types for which generalized are-consistency is sufficient to ensure the existence of a solution. We give some examples to illustrate the application of this result.
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.
暂无评论