Comparison of PBO solvers in a dependency solving domain

Paulo Trezentos
(ISCTE / ADETTI / Caixa Mágica)

Linux package managers have to deal with dependencies and conflicts of packages required to be installed by the user. As an NP-complete problem, this is a hard task to solve. In this context, several approaches have been pursued. Apt-pbo is a package manager based on the apt project that encodes the dependency solving problem as a pseudo-Boolean optimization (PBO) problem. This paper compares different PBO solvers and their effectiveness on solving the dependency solving problem.

In Inês Lynce and Ralf Treinen: Proceedings First International Workshop on Logics for Component Configuration (LoCoCo 2010), Edinburgh, UK, 10th July 2010, Electronic Proceedings in Theoretical Computer Science 29, pp. 23–31.
Published: 6th July 2010.

ArXived at: http://dx.doi.org/10.4204/EPTCS.29.3 bibtex PDF

Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org