Three different optimization criteria will be used. All three 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 ("trendy") and third ("user") criterion 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) ≠ 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}

- unsat_recommends(I,S) counts the number of disjunctions in
Recommends-fields of installed packages that are not satisfied by S:
unsat_recommends(I,S) = #{ (name,v,c) | v ∈ 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 unsat_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, unsat_recommends(I,S)=2. Note that in any case the value of unsat_recommends(I,S) only depends on S but not on I.

- sum(
*name*)(I,S) is the sum over all installed packages of the value of their field*name*, where*name*is a property of type int or of one of its subtypes (nat, posint). This property can be one of the core properties defined in the CUDF specification, or a property that is declared in the preamble of the CUDF document.sum(

*name*)(I,S) = ∑_{(p ∈ S)}p.*name*where p.

*name*denotes the value of package p for property*name*.A typical example of this would be sum(size), where size is an additional integer-valued property of packages indicating their size.

The three 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 unsat_recommends, min new)- compute ri = removed(I,Si), ui = notuptodate(I,Si), uri = unsat_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))))

*user*: we want to answer the user request, optimizing by a criterion provided by the user. The criterion is a lexicographic combination of the integer utility functions given above, each of them with a polarity ("+" for a function to maximize, "-" for a function to minimize). The functions are listed in decreasing order of priority, and separated by the symbol ",".

For instance, the paranoid criterion could be written as-removed,-changed

the trendy criterion could be written as-removed,-notuptodate,-unsat_recommends,-new

and a user of a machine with a small disk might write

-removed,-sum(installed_size),-notuptodate,-unsat_recommends,-new