While classical Constraint Satisfaction Problems (shortly, CSPs) concern the search for the boolean assignment of a set of variables that has to satisfy some given requirements, its soft variant considers more general, possibly ordered domains for assignments, thus modelling preferences: the aim is to provide an environment where suitable algorithm and properties (e.g. on constraint propagation) can be stated and proved, and thus inherited by all the instances. Besides their flexibility, these formalisms have been advocated for their modularity: suitable operators can be dened, in order to manipulate such structures and build new ones. However, some intuitive constructions were given less attention, such as lexicographic orders. Given two partially ordered domains, our work shows under which conditions a new one can be built that corresponds to the lexicographic order of those two. The result allows for a wider application of the soft formalism, and it is going to be pivotal for the use of soft constraints in modelling scenarios where more than one feature has to be satised, yet the features themselves are equipped with a fixed order of importance.

Soft constraints for lexicographic orders

GADDUCCI, FABIO;MONREALE, GIACOMA;
2013

Abstract

While classical Constraint Satisfaction Problems (shortly, CSPs) concern the search for the boolean assignment of a set of variables that has to satisfy some given requirements, its soft variant considers more general, possibly ordered domains for assignments, thus modelling preferences: the aim is to provide an environment where suitable algorithm and properties (e.g. on constraint propagation) can be stated and proved, and thus inherited by all the instances. Besides their flexibility, these formalisms have been advocated for their modularity: suitable operators can be dened, in order to manipulate such structures and build new ones. However, some intuitive constructions were given less attention, such as lexicographic orders. Given two partially ordered domains, our work shows under which conditions a new one can be built that corresponds to the lexicographic order of those two. The result allows for a wider application of the soft formalism, and it is going to be pivotal for the use of soft constraints in modelling scenarios where more than one feature has to be satised, yet the features themselves are equipped with a fixed order of importance.
9783642451133
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/11568/259151
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 13
  • ???jsp.display-item.citation.isi??? ND
social impact