Computer Science – Logic in Computer Science
Scientific paper
2010-07-07
EPTCS 29, 2010, pp. 1-10
Computer Science
Logic in Computer Science
In Proceedings LoCoCo 2010, arXiv:1007.0831
Scientific paper
10.4204/EPTCS.29.1
Upgradeability problems are a critical issue in modern operating systems. The problem consists in finding the "best" solution according to some criteria, to install, remove or upgrade packages in a given installation. This is a difficult problem: the complexity of the upgradeability problem is NP complete and modern OS contain a huge number of packages (often more than 20 000 packages in a Linux distribution). Moreover, several optimisation criteria have to be considered, e.g., stability, memory efficiency, network efficiency. In this paper we investigate the capabilities of MILP solvers to handle this problem. We show that MILP solvers are very efficient when the resolution is based on a linear combination of the criteria. Experiments done on real benchmarks show that the best MILP solvers outperform CP solvers and that they are significantly better than Pseudo Boolean solvers.
Michel Claude
Rueher Michel
No associations
LandOfFree
Handling software upgradeability problems with MILP solvers does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Handling software upgradeability problems with MILP solvers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Handling software upgradeability problems with MILP solvers will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-344748