  A common interpretation of soft constraints penalizes the database for every
violation of every constraint, where the penalty is the cost (weight) of the
constraint. A computational challenge is that of finding an optimal subset: a
collection of database tuples that minimizes the total penalty when each tuple
has a cost of being excluded. When the constraints are strict (i.e., have an
infinite cost), this subset is a "cardinality repair" of an inconsistent
database; in soft interpretations, this subset corresponds to a "most probable
world" of a probabilistic database, a "most likely intention" of a
probabilistic unclean database, and so on. Within the class of functional
dependencies, the complexity of finding a cardinality repair is thoroughly
understood. Yet, very little is known about the complexity of this problem in
the more general soft semantics. This paper makes a significant progress in
this direction. In addition to general insights about the hardness and
approximability of the problem, we present algorithms for two special cases: a
single functional dependency, and a bipartite matching. The latter is the
problem of finding an optimal "almost matching" of a bipartite graph where a
penalty is paid for every lost edge and every violation of monogamy.
