The installation of software packages (on Linux as well as in other package-driven platforms as eclipse plugins) depends on the correct resolution of dependencies and conflicts between packages. As an NP-complete problem, this is an hard task which todays technology does not address in an acceptable way. This seminar introduces a new approach to solving the software dependency problem in a Linux environment, devising a way for solving dependencies according to available packages and user preferences. We present the “apt-pbo” tool - the first available tool that solves dependencies in a complete and optimal way. The contribution is threefold. Our main finding is an efficient encoding of the dependencies and conflicts as a pseudo-boolean optimization problem without the need of ILP or SAT extra-steps. Second, we achieve this goal without sacrificing performance, a critical issue for a tool with user interaction. Finally, the developed tool is available under a free license allowing enhancement and benchmarking.

Location(s)