Two fixed optimization criteria will be used. Both are lexicographic combinations of different integer-valued utility functions of a solution, which we describe below.

Note that each of these utility functions calculates a value only from
the initial and the final installation status, that is the user
request to install or remove a certain package is not used here. The
reason for this that each proposed solution must first of all satisfy
the user request, otherwise it will be discarded and the solver will
obtain a penalty value. Only those proposed solutions that actually
*are* solutions will be compared by the optimization criteria
defined below, yielding a score according to the ranking
obtained. This is more precisely described in the ranking rules.

For the second criterion ("trendy") we will make use of an extra
package property which is not among the mandatory package properties.
This additional property is `recommends`, and it has values of
type `vpkgformula` (that is the same type as the mandatory
property `depends`). The idea is that recommended packages are
non-mandatory dependencies.

For that reason, the CUDF documents will contain a specification of that property in the document preamble, like this:

`
preamble:
property: recommends: vpkgformula = [ true! ]
`

Suppose that a solver tool outputs for the initial universe I a proposed solution S. We write V(X,name) the set of versions in which name (the name of a package) is installed in X, where X may be I or S. That set may be empty (name is not installed), contain one element (name is installed in exactly that version), or even contain multiple elements in case a package is installed in multiple versions.

We write

- #removed(I,S) is the number of packages
*removed*in the proposed solution S w.r.t. the original installation I:#removed(I,S) = #{name | V(I,name) nonempty and V(S,name) empty}

- #new(I,S)is the number of
*new*packages in the proposed solution S w.r.t. the original installation I:#new(I,S) = #{name| V(I,name) empty and V(S,name) nonempty}

- #changed(I,S) is the number of packages with a
*modified*(set of) version(s) in the proposed solution S w.r.t. the original installation I :#changed(I,S) = #{name | V(I,name) different to V(S,name) }

- #notuptodate(I,S) is the number of installed packages
but
*not*in the latest available version:#notuptodate(I,S) = #{name| V(S,name) nonempty and does not contain the most recent version of name in S}

- #unsatisfied-recommends(I,S) counts the number of disjunctions in
Recommends-fields of installed packages that are not satisfied by S:
#unsatisfied-recommends(I,S) = { (name,v,c) | v is an element of V(S,name) and (name,v) recommends ..., c, ... and c is not satisfied by S }

For instance, if package a recommends

`b, c|d|e, e|f|g, b|g, h`

and if S installs a, e, f, and h, but neither of b, c, d, or g, then one would obtain for the package a alone a value of 2 for #unsatisfied-recommends since the 2nd, 3rd and 5th disjunct of the recommendation are satisfied, and the others are not. If no other package contains recommendations that means that, in that case, #unsatisfied-recommends(I,S)=2. Note that in any case the value of #unsatisfied-recommends(I,S) only depends on S but not on I.

The two optimization criteria are

*paranoid*: we want to answer the user request, minimizing the number of packages removed in the solution, and also the packages changed by the solution; the optimization criterion is

lex( min #removed, min #changed)Hence, two solutions S1 and S2 will be compared as follows:

- compute ri = #removed(I,Si), ci = #changed(I,Si)
- S1 is better than S2 iff r1 < r2 or (r1=r2 and c1< c2)

*trendy*: we want to answer the user request, minimizing the number of packages removed in the solution, minimizing the number of outdated packages in the solution, minimizing the number of unsatisfied recommendations, and minimizing the number of extra packages installed; the optimization criterion is

lex( min #removed, min #notuptodate, min #unsatisfied-recommends, min #new)- compute ri = #removed(I,Si), ui = #notuptodate(I,Si), uri = #nusatisfied-recommends(I,Si), ni = #new(U,Si)
- S1 is better than S2 iff r1 < r2 or (r1=r2 and (u1< u2 or (u1=u2 and (uri1< uri2 or (uri1 = uri2 and n1 < n2))))