Re: RFC: The Future of Solving Dependency Problems in APT (SAT, CUDF)
Hi all,
On Thu, Dec 23, 2010 at 10:09:57AM +0100, Stefano Zacchiroli wrote:
> > I would also like to create the CudfSolver, but I'd need a solver to
> > test with. If anyone knows such solvers, please write.
>
> In the Mancoosi project we do have quite some of them, coming from the
> MISC 2010 competition http://www.mancoosi.org/misc-2010/ . In general,
> we have two variants of each participant solver, one implementing a
> "trendy" optimization strategy (try to upgrade as much packages as
> possible), and another one implementing a "paranoid" strategy (try to
> satisfy user request, but by changing as little packages as
> possible). Mind you though, as the participants were free to use the
> language they want, there's quite some Java around which is not exactly
> "fast" in CUDF parsing.
during the latest run of the misc-live (basically the same as misc-2010
but it is not an official competition) we also opened up a third track,
the "user track" where solver were asked to optimize a given expression.
Within this track we can encode the paranoid and trendy tracks. For
example the trendy track can be given by the following optimization
function :
lex( min removed, min notuptodate, min unmet_recommends, min new)
while the paranoid track as :
lex( min removed, min changed)
It think we should look at this third category of solvers as the allow
us to specify sane optimization criteria for install and upgrades.
GPL solver :
http://www.cs.uni-potsdam.de/wv/aspcud/
Eclipse licence :
http://wiki.eclipse.org/Equinox/p2/CUDFResolver
Non free solvers :( but we have the right to redistribute them :
http://sat.inesc-id.pt/~mikolas/cudf2pbo.html
http://sat.inesc-id.pt/~mikolas/cudf2msu.html
My preference is the aspcud that did pretty well in the competition and
is GPL.
It is important to notice, that picosat will be able to tell you a
solution, but probably it won't be a good one. These solvers should be
able to tell you the best solution accordingly to given objective
function.
I've also written a python prototype (mpm.py) available here as zack
mentioned :
http://gforge.info.ucl.ac.be/plugins/scmsvn/viewcvs.php/trunk/updb/mpm/?root=mancoosi
It uses a couple of external binaries to convert Packages to Cudf, but I
think we would easily integrate your script to do the job. Something
else that is left to do it to update the status file once the package is
installed... If you just want to check the solver part and run it as
normal user, you can just comment out the "commit" part. I think this
can be a nice starting point to play and settle on a correct level of
abstraction for the API.
A small whish item since we are here: can we also expose the function
that computes the installation order. It would be nice to somehow
formalize this algorithm and let the "user" access the list in some
other way then throught a debugging option...
hope this helps.
p
--
----
http://en.wikipedia.org/wiki/Posting_style
Reply to: