In previous work, a new approach called Open CSP (OCSP) was defined as a way of integrate information gathering and problem solving. Instead of collecting all variable values before CSP resolution starts, OCSP asks fo...
详细信息
ISBN:
(纸本)3540462678
In previous work, a new approach called Open CSP (OCSP) was defined as a way of integrate information gathering and problem solving. Instead of collecting all variable values before CSP resolution starts, OCSP asks for values dynamically as required by the solving process, starting from possibly empty domains. this strategy permits to handle unbounded domains keeping completeness. However, current OCSP algorithms show a poor performance. For instance, the FO-Search algorithm uses a Backtracking and needs to solve the new problem from scratch every time a new value is acquired. In this paper we improve the original algorithm for the OCSP model. Our contribution is two-fold: we incorporate local consistency and we avoid solving subproblems already explored in previous steps. Moreover, these two contributions guarantee the completeness of the algorithm and they do not increase the number of values needed for finding a solution. We provide experimental results than confirm a significant speed-up on the original approach.
the Still-Life problem is challenging for CP techniques because the basic constraints of the game of Life are loose and give poor propagation for Still-Life. In this paper, we show how ad hoc global case constraints c...
详细信息
the Still-Life problem is challenging for CP techniques because the basic constraints of the game of Life are loose and give poor propagation for Still-Life. In this paper, we show how ad hoc global case constraints can be customized to construct various models to provide much stronger propagation with CP solvers. Since we use custom ad hoc constraints of high arity where the number of tuples to define the constraint are large, the actual constraint representation becomes important to avoid excessive space consumption. We demonstrate how to use BDDs to construct good representations for the case constraint which is critical for efficiency. Our results seem comparable to hybrid CP/IP models even though we are only using propagation albeit on ad hoc global constraints. this paper shows an extensive example of how to systematically build models using different kinds of ad hoc constraints. It also demonstrates the solving potential of ad hoc global constraints.
Covering arrays can be applied to the testing of software, hardware and advanced materials, and to the effects of hormone interaction on gene expression. In this paper we develop constraintprogramming models of the p...
详细信息
Covering arrays can be applied to the testing of software, hardware and advanced materials, and to the effects of hormone interaction on gene expression. In this paper we develop constraintprogramming models of the problem of finding an optimal covering array. Our models exploit global constraints, multiple viewpoints and symmetry-breaking constraints. We show that compound variables, representing tuples of variables in our original model, allow the constraints of this problem to be represented more easily and hence propagate better. With our best integrated model, we are able to either prove the optimality of existing bounds or find new optimal solutions, for arrays of moderate size. Local search on a SAT-encoding of the model is able to find improved solutions and bounds for larger problems.
An algorithm that performs asynchronous backtracking on distributed CSPs, with dynamic ordering of agents is proposed, ABT_DO. Agents propose reorderings of lower priority agents and send these proposals whenever they...
详细信息
ISBN:
(纸本)3540292381
An algorithm that performs asynchronous backtracking on distributed CSPs, with dynamic ordering of agents is proposed, ABT_DO. Agents propose reorderings of lower priority agents and send these proposals whenever they send assignment messages. Changes of ordering triggers a different computation of Nogoods. the dynamic ordered asynchronous backtracking algorithm uses polynomial space, similarly to standard ABT. the ABT_DO algorithm withthree different ordering heuristics is compared to standard ABT on randomly generated DisCSPs. A Nogood-triggered heuristic, inspired by dynamic backtracking, is found to outperform static order ABT by a large factor in run-time and improve the network load.
the Still-Life problem is challenging for CP techniques because the basic constraints of the game of Life are loose and give poor propagation for Still-Life. In this paper, we show how ad hoc global case constraints c...
详细信息
the Still-Life problem is challenging for CP techniques because the basic constraints of the game of Life are loose and give poor propagation for Still-Life. In this paper, we show how ad hoc global case constraints can be customized to construct various models to provide much stronger propagation with CP solvers. Since we use custom ad hoc constraints of high arity where the number of tuples to define the constraint are large, the actual constraint representation becomes important to avoid excessive space consumption. We demonstrate how to use BDDs to construct good representations for the case constraint which is critical for efficiency. Our results seem comparable to hybrid CP/IP models even though we are only using propagation albeit on ad hoc global constraints. this paper shows an extensive example of how to systematically build models using different kinds of ad hoc constraints. It also demonstrates the solving potential of ad hoc global constraints.
We review the many different definitions of symmetry for constraint satisfaction problems (CSPs) that have appeared in the literature, and show that a symmetry can be defined in two fundamentally different ways: as an...
详细信息
ISBN:
(纸本)3540292381
We review the many different definitions of symmetry for constraint satisfaction problems (CSPs) that have appeared in the literature, and show that a symmetry can be defined in two fundamentally different ways: as an operation preserving the solutions of a CSP instance, or else as an operation preserving the constraints. We refer to these as solution symmetries and constraint symmetries. We define a constraint symmetry more precisely as an automorphism of a hypergraph associated with a CSP instance, the microstructure complement. We show that the solution symmetries of a CSP instance can also be obtained as the automorphisms of a related hypergraph, the k-ary nogood hypergraph and give examples to show that some instances have many more solution symmetries than constraint symmetries. Finally, we discuss the practical implications of these different notions of symmetry.
the heavy-tailed phenomenon that characterises the runtime distributions of backtrack search procedures has received considerable attention over the past few years. Some have conjectured that heavy-tailed behaviour is...
详细信息
the heavy-tailed phenomenon that characterises the runtime distributions of backtrack search procedures has received considerable attention over the past few years. Some have conjectured that heavy-tailed behaviour is largely due to the characteristics of the algorithm used. Others have conjectured that problem structure is a significant contributor. In this paper we attempt to explore the former hypothesis, namely we study how variable and value ordering heuristics impact the heavy-tailedness of runtime distributions of backtrack search procedures. We demonstrate that heavy-tailed behaviour can be eliminated from particular classes of random problems by carefully selecting the search heuristics, even when using chronological backtrack search. We also show that combinations of good search heuristics can eliminate heavy tails from quasigroups with holes of order 10 and 20, and give some insights into why this is the case. these results motivate a more detailed analysis of the effects that variable and value orderings can have on heavy-tailedness. We show how combinations of variable and value ordering heuristics can result in a runtime distribution being inherently heavy-tailed. Specifically, we show that even if we were to use an oracle to refute insoluble subtrees optimally, for some combinations of heuristics we would still observe heavy-tailed behaviour. Finally, we study the distributions of refutation sizes found using different combinations of heuristics and gain some further insights into what characteristics tend to give rise to heavy-tailed behaviour.
constraint satisfaction problems (CSPs) sometimes contain both variable symmetries and value symmetries, causing adverse effects on CSP solvers based on tree search. As a remedy, symmetry breaking constraints are comm...
详细信息
constraint satisfaction problems (CSPs) sometimes contain both variable symmetries and value symmetries, causing adverse effects on CSP solvers based on tree search. As a remedy, symmetry breaking constraints are commonly used. While variable symmetry breaking constraints can be expressed easily and propagated efficiently using lexicographic ordering, value symmetry breaking constraints are often difficult to formulate. In this paper, we propose two methods of using symmetry breaking constraints to tackle value symmetries. First, we show theoretically when value symmetries in one CSP correspond to variable symmetries in another CSP of the same problem. We also show when variable symmetry breaking constraints in the two CSPs, combined using channeling constraints, are consistent. Such results allow us to tackle value symmetries efficiently using additional CSP variables and channeling constraints. Second, we introduce value precedence, a notion which can be used to break a common class of value symmetries, namely symmetries of indistinguishable values. While value precedence can be expressed using inefficient if-then constraints in existing CSP solvers, we propose efficient propagation algorithms for implementing global value precedence constraints. We also characterize several theoretical properties of the value precedence constraints. Extensive experiments are conducted to verify the feasibility and efficiency of the two proposals.
the heavy-tailed phenomenon that characterises the runtime distributions of backtrack search procedures has received considerable attention over the past few years. Some have conjectured that heavy-tailed behaviour is...
详细信息
the heavy-tailed phenomenon that characterises the runtime distributions of backtrack search procedures has received considerable attention over the past few years. Some have conjectured that heavy-tailed behaviour is largely due to the characteristics of the algorithm used. Others have conjectured that problem structure is a significant contributor. In this paper we attempt to explore the former hypothesis, namely we study how variable and value ordering heuristics impact the heavy-tailedness of runtime distributions of backtrack search procedures. We demonstrate that heavy-tailed behaviour can be eliminated from particular classes of random problems by carefully selecting the search heuristics, even when using chronological backtrack search. We also show that combinations of good search heuristics can eliminate heavy tails from quasigroups with holes of order 10 and 20, and give some insights into why this is the case. these results motivate a more detailed analysis of the effects that variable and value orderings can have on heavy-tailedness. We show how combinations of variable and value ordering heuristics can result in a runtime distribution being inherently heavy-tailed. Specifically, we show that even if we were to use an oracle to refute insoluble subtrees optimally, for some combinations of heuristics we would still observe heavy-tailed behaviour. Finally, we study the distributions of refutation sizes found using different combinations of heuristics and gain some further insights into what characteristics tend to give rise to heavy-tailed behaviour.
暂无评论