On year ago, we (the mancoosi team) published a comparison study regarding the state of the art of dependency solving in debian. As few noticed, the data presented had few glitches that I promised to fix. So we’ve repeated our tests using exactly the same data we used one year ago, but now using the latest available versions of all package managers as available in debian unstable.

During the last year, three out of four solver that we evaluated release a major upgrade so I expected many improvements in performances and accuracy.

• apt-get 0.8.10 -> 0.9.7
• aptitude 0.6.3 -> 0.6.7
• smart 1.3-1 -> 1.4
• cupt 1.5.14.1 -> 2.5.6

Mpm, our test-bench for new technologies, changed quite a bit under the wood as a consequence of the evolution of apt-cudf and the recent work done in apt-get to integrate external cudf dependency solvers.

Overall the results of our study are not changed. All solvers but mpm, that is based on aspcud, are not scalable as the number of packages (and alternatives) grows. It seems that Smart is the solver that does not give up, incurring in a timeout (fixed at 60 seconds) most of the time. Aptitude is the solver that tried to give you a solution, doesn’t matter what and as result providing solutions that do not satisfy the user request for one reason or the other. Apt-get does surprisingly well, but it gives up pretty often showing the incomplete nature of it’s internal solver. Cupt sometimes timeout, sometimes gives up, but when it is able to provide an answer it is usually optimal and it is very fast … Mpm consistently finds an optimal solution, but sometimes it takes really a long time to do it. Since mpm is written in python and not optimized for speed this is not a big problem for us. The technology used by mpm is now integrated in apt-get and I hope this will alleviate this problem.

All the details of our study can be found one the Mancoosi Website as usual with a lot of details. For example here you can find the results when mixing four major releases : sarge-etch-lenny-squeeze.

Comments are more then welcome.

The second edition of the lo.co.co. workshop has been just announced . It will happen on September 12, 2011, in Perugia, Italy and co-located with the International Conference on Principles and Practice of Constraint Programming (CP 2011)

During the workshop it will be announced the winner(s) of the second official edition of the MISC competition (TBA).

The results of the 4th run of the misc competition are [http://mancoosi.org/misc-live/20110225/results/ online !] .

The annoncement sent on the mailing list:

This time, it was quite close, and execution times had to be taken into account several times to break ties. However, looking at the different total times for each solver it looks closer than it actually was. The reason for this is the way the “total success time” is defined (see http://www.mancoosi.org/misc-live/20110225/rules/, section “Breaking Ties”). Since we had many cases without a solution, our definition resulted in the same large constant added to the time of each participant. We’ll have to think about changing this for the next time.

We still have to decide if we’re going to have another edition of misc live before the official annual competition (TBA).

enjoy !

In december we published the results of the third run of the misc live competition on the mancoosi website. I left this post in my draft folder for a quite a while now. I’ll publish for posterity…

The main difference from the last misc competition is the introduction of a new track, the user track, where we we want to answer the user request, and look for an optimal solution according to an optimization criterion provided by the user.

The initial assessment of the results are quite positive. We received 6 submissions for the trendy and paranoid track and 4 for the user track. These are very interesting results. We don’t have a clear winner on all tracks as in the misc 2010 competition. The cudf2msu4trendy-1.0 from INESC wins the trandy and user1 track. The aspcud-paranoid-1.3 from the university of posdam is the best on the paranoid track, while cudf2pbo4user-1.0 is the winner of the track user2 and user2.

The track paranoid and trendy are the same as in misc 2010. We actually used the same problems as in misc2010 plus 4 new categories (sarge…sid) that are a collection of problems featuring the same installation request but with increasingly large number of packages and versions per packages.

A few words on the new user track. Since in this track the optimization function was given to the solver as an additional input, we decided to try out different criteria. The first one, in user1 is what I called the “Paranoid upgrade” criteria and all problems used in this track are (real) upgrade problems. In cudf the upgrade semantic allow to effectively not upgrade at all a package (since in the solution its version must be greater or equal or the version currently installed). This definition does not goes very well together with the paranoid criteria as the best solution for an upgrade would always be a solution that do not change anything. For this reason the we defined the new criteria as ‘-notuptodate,-removed,-changed’ where solutions that privilege new (upgraded) packages are preferred to solution that do not change anything at all.