Apt-pbo: Solving the Software Dependency Problem using Pseudo-Boolean Optimization
Paulo Trezentos,
ISCTE –
Abstract:
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.
Date: 2009-Sep-25 Time: 13:00:00 Room: 336
For more information:
Upcoming Events
INESC-ID ESR Talks – February 2023

If you are a masters/PhD student or a postdoctoral fellow, come and present your work in an informal and friendly environment – and savour some tasty snacks!
Individual talks will be 10-15 minutes plus time for feedback. Enroll on your selected date by emailing pedro.ferreira[at]inesc-id.pt.
Happening on the second Wednesday of every month (4pm-5pm):
- 15 February (Alves Redol, Room 9)
- 15 March (Alves Redol, Room 9)
- 12 April (Alves Redol, Room 9)
- 10 May (Alves Redol, Room 9)
- 14 June (Alves Redol, Room 9)
- 12 July (Alves Redol, Room 9)
We hope to see you there!