Representing and Reasoning with Qualitative Preferences for
  Compositional Systems
  Many applications, e.g., Web service composition, complex system design, team
formation, etc., rely on methods for identifying collections of objects or
entities satisfying some functional requirement. Among the collections that
satisfy the functional requirement, it is often necessary to identify one or
more collections that are optimal with respect to user preferences over a set
of attributes that describe the non-functional properties of the collection.
  We develop a formalism that lets users express the relative importance among
attributes and qualitative preferences over the valuations of each attribute.
We define a dominance relation that allows us to compare collections of objects
in terms of preferences over attributes of the objects that make up the
collection. We establish some key properties of the dominance relation. In
particular, we show that the dominance relation is a strict partial order when
the intra-attribute preference relations are strict partial orders and the
relative importance preference relation is an interval order.
  We provide algorithms that use this dominance relation to identify the set of
most preferred collections. We show that under certain conditions, the
algorithms are guaranteed to return only (sound), all (complete), or at least
one (weakly complete) of the most preferred collections. We present results of
simulation experiments comparing the proposed algorithms with respect to (a)
the quality of solutions (number of most preferred solutions) produced by the
algorithms, and (b) their performance and efficiency. We also explore some
interesting conjectures suggested by the results of our experiments that relate
the properties of the user preferences, the dominance relation, and the
algorithms.
