CNF Instances from the Software Package Installation Problem.
Josep Argelich, Inês Lynce · 2008
The complexity of software package installations poses a number of key challenges. Very often it is not possible to install all the desired packages and a variety of solutions can be thought of. Recent work has suggested the optimization of a user-provided objective function. The present work aims at characterizing the CNF instances resulting from the software package installation problem. Starting from a basic configuration, different installations have been generated by adding a subset of the most popular packages. We have studied the hardness of satisfiable and unsatisfiable instances, as well as the unsatisfiable cores of the unsatisfiable instances and the maximum number of packages that can be installed when the instance is unsatisfiable. The obtained results shed additional light on optimization criteria to solve installation conflicts. 1