Comparison of PBO solvers in a dependency solving domain
arXiv:1007.1022 · doi:10.4204/EPTCS.29.3
Abstract
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 Proceedings LoCoCo 2010, arXiv:1007.0831