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.

Additional package property

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! ]

Definition of the utility functions

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.

Definition of the optimization criteria

The three optimization criteria are

  1. 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:

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

  2. 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)

    Hence, two solutions S1 and S2 will be compared as follows:
    1. compute ri = removed(I,Si), ui = notuptodate(I,Si), uri = unsat_recommends(I,Si), ni = new(U,Si)
    2. 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))))

  3. 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