Comparison of PBO solvers in a dependency solving domain

Software installation is the process of installing programs assuring that specifically required software is pre-installed and that defined actions are taken before or after the copy of the files into the file-system [22, 24]. Although this is a common problem among Microsoft and Open Source Operating Systems (GNU/Linux, BSD,...) [25] we will focus on the later ones, since a progress in this field would be applicable to all environments, including applications like Eclipse or Firefox [15].The installation process comprises retrieving the package, solving the software dependency tree, retrieving and installing the software dependencies and finally installing the package and executing the associated install scripts [8].The dependency graph represents the software dependencies and sub-dependencies needed for a package to work properly after installation [5]. The restrictions imposed by the graph may have no solution (for instance, due to broken dependencies), only one solution, or several solutions. Criteria such as the minimum number of packages or freshness can be defined to rank the solutions in terms of their quality. Finding a solution consists in defining the sub-set of packages that meets the dependency requirements. This process is called dependency solving. One approach to dependency solving is to encode the problem as a pseudo-Boolean optimization (PBO) problem using existing solvers for finding the optimal solutions. This approach is applied in apt-pbo, a meta-installer tool based on apt that will be described in this paper.This paper is organized as follows. In section 2 we provide background information about PBO. Section 3 depicts the apt-pbo tool and its architecture. Section 4 presents empirical results of experiments conducted with the several solvers. Finally, in section 6 are presented the concluding remarks.