You are here

Search heuristics and optimisations to solve package installability problems by constraint programming

TitleSearch heuristics and optimisations to solve package installability problems by constraint programming
Publication TypeMiscellaneous
Year of Publication2006
AuthorsMouthuy, Sébastien, Quesada Luis, and Dooms Grégoire
Abstract

The aim of this work is to present a constraint programming formulation of the package installability problem. The package installability problem deals about de- termining whether a package of a repository could be installed or not. This problem is known to be NP-complete.Efficient search heuristics will be presented, leading to few failures. Our solver is able to determine whether all packages of the Debian distribution can be installed in less than 6 minutes. At the end, implementation of optimisation criteria are also presented.