Nowadays, constraint processing has become a mayor issue in engineering applications based on digital product models. A modern product naturally decomposes into numerous subcomponents, the physical behaviour of which ...
详细信息
constraints have played a central role in cp because they capture key substructures of a problem and efficiently exploit them to boost inference. this paper intends to do the same thing for search, proposing constrain...
详细信息
constraints have played a central role in cp because they capture key substructures of a problem and efficiently exploit them to boost inference. this paper intends to do the same thing for search, proposing constraint-centered heuristics which guide the exploration of the search space toward areas that are likely to contain a high number of solutions. We first propose new search heuristics based on solution counting information at the level of individual constraints. We then describe efficient algorithms to evaluate the number of solutions of two important families of constraints: occurrence counting constraints, such as all different, and sequencing constraints, such as regular. In both cases we take advantage of existing filtering algorithms to speed up the evaluation. Experimental results on benchmark problems show the effectiveness of our approach.
A constraint satisfaction problem is defined by a set of variables associated to domains,and a set of constraints on these variables. Solving a constraint satisfaction problem consists in finding assignments of all va...
ISBN:
(纸本)3540428631
A constraint satisfaction problem is defined by a set of variables associated to domains,and a set of constraints on these variables. Solving a constraint satisfaction problem consists in finding assignments of all variables that satisfy all constraints. Since this problem is NP-hard,constraint propagation has been designed to struggle against the combinatorial explosion of brute-force search by pruning domains before enumeration. Filtering algorithms enforcing consistency properties [8]are the most well-known techniques for constraint propagation.
One of the key factors in the efficiency of backtracking algorithms is the rule they use to decide on which variable to branch next (namely, the variable ordering heuristics). In this paper, we give a formulation of d...
详细信息
In the scope of distributed constraint reasoning, the main algorithms presented so far have a feature in common: the addition of links between previously unrelated agents, before or during search. Our work presents a ...
详细信息
In this paper we have modeled tradeoffs in constraint-based configuration as additional constraints, and begun to study the issues involved in generating and evaluating such tradeoffs. We describe our basic approach i...
详细信息
A difficulty that arises frequently when writing a constraint solver is to determine the constraint propagation and simplification algorithm. In previous work, different methods for automatic generation of propagation...
详细信息
the paper presents propagation rules that are common to the minimum constraint family and to the number of distinct values constraint family. One practical interest of the paper is to describe an implementation of the...
详细信息
the constraint propagation process is a powerful tool for solving constraint satisfaction problems (CSPs). We propose a filtering technique which exploits at best this tool in order to improve the pruning efficiency. ...
详细信息
Recently, constraint-programming techniques have been used to generate test data and to verify the conformity of a program with its specification. constraint generated for these tasks may involve integer ranging on al...
详细信息
ISBN:
(纸本)9783540749691
Recently, constraint-programming techniques have been used to generate test data and to verify the conformity of a program with its specification. constraint generated for these tasks may involve integer ranging on all machine-integers, thus, the constraint-based modeling of the program and its specification is a critical issue. In this paper we investigate different models. We show that a straightforward translation of a program and its specification in a system of guarded constraints is ineffective. We outline the key role of Boolean abstractions and explore different search strategies on standard benchmarks.
暂无评论