THE RULES OF THE GAME

Optimization critera:

Two fixed optimization criteria are used in this version of the competition: they are both lexicographic combinations of four simple integer valued utility functions of a solution, which we describe below.

Let's call U the universe of a CUDF, which contains the description of all available packages, and the field Installed: which is set to 1 for packages installed on the user machine, and 0 otherwise.

Let's call S a solution to the user request computed by your solver.

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 U or S. That set may be empty (name is not installed), contain one element (name is installed in exactely that version), or even contain multiple elements in case a package is installed in multiple versions.

We write

  • #removed(U,S): is the number of packages removed in the proposed solution S w.r.t. the original installation U :

    #removed(U,S) = #{name | V(U,name) nonempty and V(S,name) empty}

  • #new(U,S): is the number of new packages in the proposed solution S w.r.t. the original installation U :

    #new(U,S) = #{name| V(U,name) empty and V(S,name) nonempty}

  • #changed(U,S): is the number of packages with a modified (set of) version(s) in the proposed solution S w.r.t. the original installation U :

    #changed(U,S) = #{name | V(U,name) different to V(S,name) }

  • #notuptodate(U,S): is the number of installed packages but not in the latest available version :

    #notuptodate(U,S) = #{name| V(S,name) nonempty and does not contain the most recent version of name in S}

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:

       i) compute ri = #removed(U,Si), ci = #changed(U,Si)

       ii) 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, minimising the number of outdated packages in the solution, and minimizing the number of extra packages installed; the optimization criterion is

            lex( min #removed, min #notuptodate, min #new)

       Hence, two solutions S1 and S2 will be compared as follows:

       i) compute ri = #removed(U,Si), ui = #notuptodate(U,Si),
          ni = #new(U,Si)

       ii) S1 is better than S2 iff
           r1 < r2 or (r1=r2 and (u1<u2 or (u1=u2 and n1<n2)))

Determining the winner on the competition data sets

All participating solvers will be executed on the same set of input problems. The exact number of input problems remains to be determined. The solvers will be ranked as follows: let m be the number of participating solvers.

For each input problem we give points to each solver, according to whether the participant yields

(1) a claimed solution that really is a solution (2) FAIL (that is, the solver declares that he hasn't found a solution) (3) abort (timeout, segmentation fault, ...) (4) a claimed solution, which in reality is not a solution to the problem

The solvers in case (1) are ordered according to the optimization criterion (best solution first), and a participant in case (1) gets the number of points that corresponds to his position in that list. For example, if solvers A, B, C, D have found a valid solution, if the solution of A is the best, the ones found by B and C are equally good, and the one found by D is the worst, then A gets 1, B and C both get 2, and D gets 4.

A participant in case (2) gets 2*m points A participant in case (3) gets 3*m points A participant in case (4) gets 4*m points

The total score of a solver is the sum of the number of points obtained. The solver with the minimal score wins.

Note that it is possible that an input problem indeed doesn't have a solution. In that case, (1) above is not possible, so the solvers that correctly say FAIL are ranked best.

Training sets

There are two training data sets available for the mini-competition (these are not the problem sets that we will be using in the real competition, but you need them to test that your solver performs correctly). These are randomly generated problems simulating possible upgrade requests of a real debian machine, using different repositories

  • rand.biglist : upgrades using packages from etch + testing + unstable
  • rand.smallist : upgrades using packages from testing + unstable
  • rand.newlist : upgrades using packages from etch + testing + unstable

They are available http://data.mancoosi.org/cudf">here.

Technical Information

All solvers must be able to treat as input a CUDF 2.0 document and output a solution in the form of another CUDF 2.0 document containing a new universe of packages satisfying the request.

The resources you need to parse CUDF 2.0 files are available on the web software.

The first useable version is libCUDF 0.5.92, downloadable as cudf_0.5.92.tar.gz but you may also get the latest development version on the forge here libcudf.

Bindings are available for C, the library is natively OCaml, see the INSTALL and README files.

For Debian users, packages are already available (see the web page).

A primer for CUDF is available at http://www.mancoosi.org/cudf/primer/

The (long) specification of CUDF, if you have any doubts, is here: http://www.mancoosi.org/reports/tr3.pdf.

Submitting solvers

The instructions on how to submit your solvers to the competition are available here.