Substitutability and interchangeability in constraint satisfaction problems (CSPs) have been used as a basis for search heuristics, solution adaptation and abstraction techniques. In this paper, we consider how the same concepts can be extended to soft constraint satisfaction problems (SCSPs). We introduce the notions of threshold α and degradation δ for substitutability and interchangeability. In αinterchangeability, values are interchangeable in any solution that is better than a threshold α, thus allowing to disregard differences among solutions that are not sufficiently good anyway. In δinterchangeability, values are interchangeable if their exchange could not degrade the solution by more than a factor of δ. Theorems, algorithms to compute (δ/α)interchangeable sets of values, and a more general treatment of all the ideas presented in this paper can be found in [2].

Interchangeability in Soft CSPs

BISTARELLI, Stefano;
2002

Abstract

Substitutability and interchangeability in constraint satisfaction problems (CSPs) have been used as a basis for search heuristics, solution adaptation and abstraction techniques. In this paper, we consider how the same concepts can be extended to soft constraint satisfaction problems (SCSPs). We introduce the notions of threshold α and degradation δ for substitutability and interchangeability. In αinterchangeability, values are interchangeable in any solution that is better than a threshold α, thus allowing to disregard differences among solutions that are not sufficiently good anyway. In δinterchangeability, values are interchangeable if their exchange could not degrade the solution by more than a factor of δ. Theorems, algorithms to compute (δ/α)interchangeable sets of values, and a more general treatment of all the ideas presented in this paper can be found in [2].
2002
3540441204
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11391/142687
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? ND
social impact