constraintprogramming is a powerful programming paradigm with a great impact on a number of important areas such as logic programming [45], concurrent programming [42], artificial intelligence [12], and combinatorial...
详细信息
ISBN:
(纸本)3540462678
constraintprogramming is a powerful programming paradigm with a great impact on a number of important areas such as logic programming [45], concurrent programming [42], artificial intelligence [12], and combinatorial optimization [46]. We believe that constraintprogramming is also a rich source of many challenging algorithmic problems, and co-operations between the constraintprogramming and the algorithms communities could be beneficial to both areas.
In this paper, we extend the principle of symmetry to dominance in Not-Equals constraint Networks and show how dominated values are detected and eliminated efficiently at each node of the search tree.
ISBN:
(纸本)3540462678
In this paper, we extend the principle of symmetry to dominance in Not-Equals constraint Networks and show how dominated values are detected and eliminated efficiently at each node of the search tree.
We describe some new propagators for breaking symmetries in constraint satisfaction problems. We also introduce symmetry breaking constraints to deal with symmetries acting simultaneously on variables and values, cond...
详细信息
ISBN:
(纸本)3540462678
We describe some new propagators for breaking symmetries in constraint satisfaction problems. We also introduce symmetry breaking constraints to deal with symmetries acting simultaneously on variables and values, conditional symmetries, as well as symmeties acting on set and other types of variables.
the paper introduces the MST(G, T, W) constraint, which is specified on two graph variables G and T and a vector W of scalar variables. the constraint is satisfied if T is a minimum spanning tree of G, where the edge ...
详细信息
ISBN:
(纸本)3540462678
the paper introduces the MST(G, T, W) constraint, which is specified on two graph variables G and T and a vector W of scalar variables. the constraint is satisfied if T is a minimum spanning tree of G, where the edge weights are specified by the entries of W. We develop algorithms that filter the domains of all variables to bound consistency.
We extend the common depth-first backtrack search for constraint satisfaction problems with randomized variable and value selection. the resulting methods are applied to real-world instances of the tail assignment pro...
详细信息
ISBN:
(纸本)3540462678
We extend the common depth-first backtrack search for constraint satisfaction problems with randomized variable and value selection. the resulting methods are applied to real-world instances of the tail assignment problem, a certain kind of airline planning problem. We analyze the performance impact of these extensions and, in order to exploit the improvements, add restarts to the search procedure. Finally computational results of the complete approach are discussed.
the problem of finding a graceful labelling of a graph, or proving that the graph is not graceful, has previously been modelled as a CSP. A new and much faster CSP model of the problem is presented, with several new r...
详细信息
ISBN:
(纸本)3540462678
the problem of finding a graceful labelling of a graph, or proving that the graph is not graceful, has previously been modelled as a CSP. A new and much faster CSP model of the problem is presented, with several new results for graphs whose gracefulness was previously unknown. Several classes of graph that are conjectured to be graceful only for small instances are investigated: after a certain size, it appears that for some of these classes the search to prove that there is no graceful labelling is essentially the same for each successive instance. the possibility of constructing a proof of the conjecture based on the search is discussed.
Efficient constraint propagation is crucial to any constraint solver. We show that watched literals, already a great success in the satisfiability community, can be used to provide highly efficient implementations of ...
详细信息
ISBN:
(纸本)3540462678
Efficient constraint propagation is crucial to any constraint solver. We show that watched literals, already a great success in the satisfiability community, can be used to provide highly efficient implementations of constraint propagators. We describe three important aspects of watched literals as we apply them to constraints, and how they are implemented in the MINION constraint solver. We show three successful applications of to constraint propagators: the sum of Boolean variables;GAC for the 'element' constraint;and GAC for the 'table' constraint.
this paper presents high-level abstractions for nondeterministic search in C++ which provide the counterpart to advanced features found in recent constraint languages. the abstractions have several benefits: they expl...
详细信息
ISBN:
(纸本)3540462678
this paper presents high-level abstractions for nondeterministic search in C++ which provide the counterpart to advanced features found in recent constraint languages. the abstractions have several benefits: they explicitly highlight the nondeterministic nature of the code, provide a natural iterative style, simplify debugging, and are efficiently implementable using macros and continuations. their efficiency is demonstrated by comparing their performance withthe C++ library GECODE, both for programming search procedures and search engines.
暂无评论