I cannot add much - The Guru has spoken :)
I'll just try to answer the question.
Daniel Le Berre wrote:
Hi Gilles,
Gilles Scokart a �crit :
Thanks to remind us the mathematic curses :-)
But I have some questions :
What does the '>=' constraints represent ?
-b1 + a1 >=0
-b2 + a1 >=0
-b3 + a1 >=0
-c1 + a1 >=0
-b2 + a1 >=0
the variables are boolean (can only take 0/1 values).
Those constraints are thus called pseudo boolean equations.
In this case, they simply represent clauses:
b1 -> a1
b2 -> a1
etc.
If I take -b1 + a1 >=0, I interpret it as "if I take b1, I must take
a1". I fail to see why you are adding this contraints to your
equation?
I agree.
I would have expected a system of contraints :
a1 = b1 + b2 + b3 (If I take a1, I also take one and exactly one of b1,b2,b3)
a1 = c1 + c2 (idem for c)
a1 = 1 (it is the root. I take it)
Usually, you need implications, no equivalences:
Here is how it is encoded for Eclipse p2
(almost, some details are missing)
// dependencies
a1 -> b1 or b2 or b3
a1 -> c1 or c2
// just require one version
b1 + b2 + b3 <= 1
c1 + c2 <= 1
The tree could be walked in two directions, and these approaches are
equivalent, except for b and c optionality:
Representation #1: P2
a1 -> b1 or b2 or b3
a1 -> c1 or c2
b1 + b2 + b3 <= 1 # this one implicates that b is optional
c1 + c2 <= 1 # this one implicates that c is optional
Representation #2: Mercury
b1 -> a1
b2 -> a1
b3 -> a1
c1 -> a1
c2 -> a1
b1 + b2 + b3 = 1
c1 + c2 + c3 = 1
In the second one it's easier for me to keep the tabs on the generated
system. Timewise both are solved in 10s of millis.
// what do I want to install?
a1 = 1
It is important to use inequalities instead of an equalities for the
versions
else any solution would force one version of each package to be installed,
independently of the packages the user would like to install.
I'm also wondering how to interpret your optimization function. I see
that you favor higher versions, but why not Min (4*b1+2*b2+b3 +
2*c2+c1) for example?
I fail to understand why it would be much more important to select the
latest version of b, than the latest version of c. Is there any
reason or is my interpretation of the function incorrect ?
Because then, you are not deterministic: the solver would consider of
equal importance to install b3 or c2 so if you cannot install both of
them, on some computers the installation would be b3 c1 and on others c2
b2. I guess you would like to avoid this :)
The big trouble is to find a metric that allow to sort the packages
in a meaningful way.
This is troublesome, so we had to make special arrangements to make
selection consistent between say, Java5 and Java6. See
http://jira.codehaus.org/browse/MERCURY-40 The pending solutions might
be #1 "the first seen GA", or #2 "sort by GA" - for now it's #1, but -
as indicated in MERCURY-40, it depends on the tree builder doing that.
Daniel
Did you have any link where I could find more explanation on the
rational of the equations?
Check Wikipedia for "Satisfiability problem", especially - pseudo
boolean approach. Took me several weeks to fully understand the beauty
of this approach, before that I tried to solve the problem myself (your
next question below).
Also, how do you solve the problem that different version might have
dependency different tree? Did you build the complete "dirty tree"
(meanings that you look up for transitive dependencies of all old
versions that will probably not be selected, an then resolve big the
equations globaly), or did you proceeds somehow iteratively (resolving
some equations to know which part of the tree to "dirty tree" to
extends, update the dirty tree with dependencies of only resolved
revisions, update the equations, solve equations again, ...).
I create a full "dirty tree" for every version, then use them all in the
generated system of inequavions. I tried to do some iterative
optimizations in the process, but SAT does better job and it is also
defined to work on the huge problems - ours is a toy for it.
Manual intervention also proved turned sour because Mercury is flexible
to allow different selection policies: default is "shallowest", then
"newest", but it's all configurable with a set of comparators, passed to
the solver. And if the need comes - we can cover a lot of exotic
variations, the first one coming to mind - "maven2 compatibility mode"
comparator. Maven2 selects the first version on the same level, Mercury
- the newest.
Thanks Daniel for all his help!
Oleg
Gilles Scokart
2008/12/19 Oleg Gusakov <oleg.subscripti...@gmail.com>:
a diagram of mercury inner workflow is here:
http://blogs.sonatype.com/people/?p=1016
fyi - I am also working on re-introducing the "old" maven-ant syntax to
mercury-ant-tasks. Herve - as you wished!
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscr...@maven.apache.org
For additional commands, e-mail: dev-h...@maven.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscr...@maven.apache.org
For additional commands, e-mail: dev-h...@maven.apache.org
