| Re: [p2-dev] MISC 2010 News |
For those who wonder what paranoid means, it is the name of one of the optimisation function that was defined by the organisers of the competition.
The competition also defined a second optimisation function called trendy. Here is the definition of those two functions as provided by the organisers.
Optimization critera:
---------------------
Two fixed optimization criterias will be 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) nonempy}
- #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)))
Daniel Le Berre ---09/01/2010 03:55:47 AM---preliminary raw results are available here:
From: | Daniel Le Berre <leberre@xxxxxxxxxxxxxxxxxxx> |
To: | P2 developer discussions <p2-dev@xxxxxxxxxxx> |
Date: | 09/01/2010 03:55 AM |
Subject: | Re: [p2-dev] MISC 2010 News |
