Constraint propagation for ordering, abstraction, and aggregation relations
Titel:
Constraint propagation for ordering, abstraction, and aggregation relations
Auteur:
Pape, Claude Le
Verschenen in:
Journal of experimental & theoretical artificial intelligence
Paginering:
Jaargang 10 (1998) nr. 1 pagina's 63-76
Jaar:
1998-01-01
Inhoud:
. Characteristics of the relation that links two or more variables of a constraint satisfaction problem can often be exploited to: reduce the computational burden of constraint propagation; avoid the instantiation of some auxiliary variables during the search for a solution; retain some flexibility in the 'solution', i.e. provide some specification for a set of solutions, rather than a unique solution to the problem under consideration; and provide a simpler explanationof the failure when it is proven that a given set of constraints conflict, i.e. cannot be simultaneously satisfied. The ability to test whether a subset of the constraints is consistent is important to determine which contraints conflict. This paper studies the particular cases of ordering, abstraction, and aggregation constraints. The consistency problem with both strict and non-strict inequalities is shown to be polynomial for totally ordered sets, but NP-hard in the case of partially ordered sets. The consistency problem for abstraction and aggregation relations is also shown to be NP-hard, and a particular polynomial case is proposed, with possible applications in design and configuration.
Tijdschrift beschrijving