Uppgraderingsproblem är en viktig fråga i moderna operativsystem. Problemet består i att hitta den "bästa" lösningen enligt vissa kriterier, att installera, ta bort eller uppgradera paket i en viss installation. Detta är ett svårt problem: komplexiteten i uppgraderingsproblemet är NP komplett och moderna operativsystem innehåller ett stort antal paket (ofta mer än 20 000 paket i en Linuxdistribution). Dessutom måste flera optimeringskriterier beaktas, t.ex. stabilitet, minneseffektivitet och näteffektivitet. I detta dokument undersöker vi förmågan hos MILP-lösare att hantera detta problem. Vi visar att MILP-lösare är mycket effektiva när upplösningen baseras på en linjär kombination av kriterierna. Experiment som görs på verkliga riktmärken visar att de bästa MILP-lösarna överträffar CP-lösarna och att de är betydligt bättre än Pseudo Boolean-lösarna.
Som en del av projektet undersökte författarna till REF förmågan hos MILP-lösare att hantera uppgraderingsproblem och visade vissa förbättringar vid pseudo-booleska optimeringar.
Handling software upgradeability problems with MILP solvers
{'venue': 'EPTCS 29, 2010, pp. 1-10', 'journal': None, 'mag_field_of_study': ['Computer Science']}