Towards efficient optimization in package management systems

Alexey Ignatiev, Mikolá Janota, Joao Marques-Silva

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

14 Citations (Scopus)


Package management as a means of reuse of software artifacts has become extremely popular, most notably in Linux distributions. At the same time, successful package management brings about a number of computational challenges. Whenever a user requires a new package to be installed, a package manager not only installs the new package but it might also install other packages or uninstall some old ones in order to respect dependencies and conflicts of the packages. Coming up with a new configuration of packages is computationally challenging. It is in particular complex when we also wish to optimize for user preferences, such as that the resulting package configuration should not differ too much from the original one. A number of exact approaches for solving this problem have been proposed in recent years. These approaches, however, do not have guaranteed runtime due to the high computational complexity of the problem. This paper addresses this issue by devising a hybrid approach that integrates exact solving with approximate solving by invoking the approximate part whenever the solver is running out of time. Experimental evaluation shows that this approach enables returning high-quality package configurations with rapid response time.

Original languageEnglish
Title of host publication36th International Conference on Software Engineering (ICSE 2014) - Proceedings
EditorsPankaj Jalote, Lionel Briand, André van der Hoek
Place of PublicationNew York NY USA
PublisherAssociation for Computing Machinery (ACM)
Number of pages11
ISBN (Electronic)9781450327565
Publication statusPublished - 2014
Externally publishedYes
EventInternational Conference on Software Engineering 2014 - Hyderabad, India
Duration: 31 May 20147 Jun 2014
Conference number: 36th


ConferenceInternational Conference on Software Engineering 2014
Abbreviated titleICSE 2014
Internet address


  • MaxSAT solving
  • Minimal Correstion Subsets
  • Optimization
  • Package management
  • SAT solving

Cite this