Common Linux distributions often include package management tools such as apt-get in Debian or yum in RedHat. Using information about package dependencies and conflicts, such tools can determine how to install a new package (and its dependencies) on a system of already installed packages. Because of the complexity in the dependencies and conflicts, such tools typically use heuristics and are therefore incomplete, in that even if a package is installable, the tool may not find out how to do it. Furthermore, if there are multiple ways of installing a given package, current tools arbitrarily pick between them without taking any user preferences into account. Such preferences could for example include picking smaller packages if the user has limited download bandwidth, or newer packages if the user wants the newest possible system. Using off-the-shelf SAT solvers, pseudo-boolean solvers, and Integer Linear Programming solvers, we have developed a new package-management tool, called opium, that improves on current tools in two ways: (1) opium is complete, in that if there is a solution, opium is guaranteed to find it, and (2) opium can optimize a user-provided objective function, which could for example state that smaller packages should be preferred over larger ones. We performed a comparative study of our tool against Debian's apt-get on 600 traces of real-world package installations. We show that opium runs fast enough to be usable, and that its completeness and optimality guarantees provides concrete benefits to end users.
Proceedings of the 29th ACM/IEEE International Conference on Software Engineering (ICSE), IEEE Computer Society Press, 2007. (to appear)