Computer Science ›› 2020, Vol. 47 ›› Issue (6): 16-23.doi: 10.11896/jsjkx.200400027

• Intelligent Software Engineering • Previous Articles     Next Articles

Multi-objective Optimization Methods for Software Upgradeability Problem

ZHAO Song-hui, REN Zhi-lei, JIANG He   

  1. School of Software,Dalian University of Technology,Dalian,Liaoning 116600,China
  • Received:2020-03-07 Online:2020-06-15 Published:2020-06-10
  • About author:ZHAO Song-hui,born in 1995,postgra-duate,is a student member of China Computer Federation.His main research interests include multi-objective optimization and search-based software engineering.
    REN Zhi-lei,born in 1984,Ph.D,asso-ciate professor,is a member of China Computer Federation.His main research interests include evolutionary computation,automatic algorithm configuration,data mining,and data analysis in software engineering.

Abstract: Open-source Package management as a means of reuse of software artifacts has become extremely popular,most notably in Linux distributions.Software upgradeabilty problem is a significant challenge which package management system must resolve.This problem aims to find the most suitable upgrade scheme that satisfies upgrade requests from users.An upgrade scheme comprises of a sequence of operations,including installing,removing,and/or upgrading packages.In the existing approaches for solving this problem,multiple upgrade requests are handled in aggregate ways.Hence,a potential risk of such approaches is that,the relationships between different upgrade objectives may not be considered properly.This paper introduces a novel approach SATMOEA,which forms software upgradeability problem as a SAT plus multi-objective optimization problem and addresses this problem combining constraint solving and multi-objective search-based optimization algorithms.We evaluate it on real instances provided by MISC (Mancoosi International Solver Competitions) and obtain promising results where we can find some Pareto optimal solutions for a complex instance with myriad constraints in a single run.In comparison with other solvers,it can provide more solutions with better diversity property to satisfy requirements in different scenarios.

Key words: Software upgradeability problem, Multi-objective optimization, SAT solving, Search-based software engineering, Software repository

CLC Number: 

  • TP311
[1]Debian -The Universal Operating System [EB/OL].(2020-03-26)[2020-03-26].https://www.d
[2]IGNATIEV A,JANOTA M,MARQUES-SILVA J.Towards efficient optimization in package management systems[C]//Proceedings of the 36th International Conference on Software Engineering.2014:745-755.
[3]REN Z,JIANG H,XUAN J,et al.Analyzing Inter-objective Relationships:A Case Study of Software Upgradability[C]//International Conference on Parallel Problem Solving from Nature.Cham:Springer,2016:442-452.
[4]TUCKER C,SHUFFELTON D,JHALA R,et al.Opium:Optimal package install/uninstall manager[C]//29th International Conference on Software Engineering (ICSE’07).IEEE,2007:178-188.
[5]ROBERTO D C.How to manage your software upgrades:tales from the Mancoosi frontline[EB/OL].(2010-04-19)[2020-03-26].
[6]MANCINELLI F,BOENDER J,DI COSMO R,et al.Managing the complexity of large free and open source package-based software distributions[C]//Twenty-First IEEE/ACM International Conference on Automated Software Engineering (ASE’06).IEEE,2006:199-208.
[7]ARGELICH J,MANYA F.Partial Max-SAT solvers with clause learning[C]//International Conference on Theory and Applications of Satisfiability Testing.Berlin:Springer,2007:28-40.
[8]ARGELICH J,LYNCE I,MARQUES-SILVA J.On solving Boolean multilevel optimization problem-s[C]//Twenty-First International Joint Conference on Artificial Intelligence.2009.
[9]LE BERRE D,RAPICAULT P.Dependency mana-gement for the eclipse ecosystem:eclipse p2,metadata and resolution[C]//Proceedings of the 1st international workshop on Open component eco-systems.2009:21-30.
[10]TREZENTOS P,LYNCE I,OLIVEIRA A L.Apt-pbo:solving the software dependency problem using pseudo-boolean optimization[C]//Proceedings of the IEEE/ACM international conference on Automated software engineering.2010:427-436.
[11]RALF T,STEFANO Z.Common Upgradeability Description Format (CUDF) 2.0[EB/OL].(2009-11-24)[2020-03-26]. /tr3.pdf.
[12]MICHEL C,RUEHER M.Handling software upgradeability problems with MILP solvers[J].Electronic Proceedings in Theoretical Computer Science,2010,29(1):1-10.
[13]GEBSER M,KAMINSKI R,SCHAUB T.aspcud:A linux package configuration tool based on answer set programming[J].Electronic Proceedings in Theoretical Computer Science,2011,65(2):12-25.
[14]ARGELICH J,BERRE D L,LYNCE I,et al.Solving Linux upgradeability problems using boolean optimization[J].Electronic Proceedings in Theoretical Computer Science,2010,29(2):11-22.
[15]JANOTA M,LYNCE I,MANQUINHO V,et al.PackUp:Tools for package upgradability solving[J].Journal on Satisfiability,Boolean Modeling and Computation,2012,8(1/2):89-94.
[16]HARMAN M.The current state and future of search based software engineering[C]//Future of Software Engineering (FOSE’07).IEEE,2007:342-357.
[17]DURILLO J J,ZHANG Y Y,ALBA E,et al.A study of the multi-objective next release problem[C]//2009 1st InternationalSymposium on Search Based Software Engineering.IEEE,2009:49-58.
[18]WALCOTT K R,SOFFA M L,KAPFHAMMER G M,et al.Timeaware test suite prioritization[C]//Proceedings of the 2006 international symposium on Software testing and analysis.2006:1-12.
[19]SARRO F,PETROZZIELLO A,HARMAN M.Multi-objective software effort estimation[C]//2016 IEEE/ACM 38th International Conference on Software Engineering (ICSE).IEEE,2016:619-630.
[20]HENARD C,PAPADAKIS M,HARMAN M,et al.Combining multi-objective search and constraint solving for configuring large software product lines[C]//2015 IEEE/ACM 37th IEEE International Conference on Software Engineering.IEEE,2015,1:517-528.
[21]DUTRA R,LAEUFER K,BACHRACH J,et al.Efficient sampling of SAT solutions for testing[C]//2018 IEEE/ACM 40th International Conference on Software Engineering (ICSE).IEEE,2018:549-559.
[22]MANCOOSI project.International Solver Competition 2012 [EB/OL].[2020-03-26].http://ww
[23]DURILLO J J,NEBRO A J.jMetal:A Java framework for multi-objective optimization[J].Advances in Engineering Software,2011,42(10):760-771.
[24]JIANG S J,WANG L S,XUE M,et al.Test Case Generation Based on Combination of Schema Using Particle Swarm Optimization[J].Journal of Software,2016,27(4):785-801.
[25]BAO X A,BAO C,JIN Y T,et al.Com-binatorial Test Case Generation Method Based on Simplified Particle Swarm Optimization with Dynamic Adjustment[J].Computer Science,2018,45(11):199-200.
[26]XUAN J F,REN Z L,WANG Z Y,et al.Progress on approaches to automatic program repair[J].Journal of Software,2016,27(4):771-784.
[27]ZHOU M Q,JIANG G H.New Spectrum-based Fault Localization Method Combining Hitting Set and Genetic Algorithm[J].Computer Science,2018,45(9):207-212.
[28]LU H,ZHANG L,YUE T.Differential IBEA for non-conformity resolution in interactive CPS production line configuration[J].Journal of Software,2016,27(4):901-915.
[29]XIANG Y,ZHOU Y R,CAI S W.Integrating Preference in Many-objective Optimal Software Product Selection Algorithm[J].Journal of Software,2020,31(2):282-301.
[30]MENG F C,CHU D H,LI K Q,et al.Solving SaaS components optimization placement problem with hybrid genetic and simulated annealing algorithm[J].Journal of Software,2016,27(4):916-932.
[31]ZHENG Y J,ZHANG B,XUE J Y.Selection of key software components for formal development using water wave optimization[J].Journal of Software,2016,27(4):933-942.
[32]SAYYAD A S,MENZIES T,AMMAR H.On the value of user preferences in search-based software engineering:a case study in software product lines[C]//2013 35th International Conference on Software Engineering (ICSE).IEEE,2013:492-501.
[33]ZITZLER E,THIELE L.Multiobjective evolutionary algorithms:a comparative case study and the strength Pareto approach[J].IEEE Transactions on Evolutionary Computation,1999,3(4):257-271.
[34]DEB K,PRATAP A,AGARWAL S,et al.A fast and elitist multi objective genetic algorithm:NSGA-II[J].IEEE Transactions on Evolutionary Computation,2002,6(2):182-197.
[1] ZHANG Qing-qi, LIU Man-dan. Multi-objective Five-elements Cycle Optimization Algorithm for Complex Network Community Discovery [J]. Computer Science, 2020, 47(8): 284-290.
[2] ZHENG You-lian, LEI De-ming, ZHENG Qiao-xian. Novel Artificial Bee Colony Algorithm for Solving Many-objective Scheduling [J]. Computer Science, 2020, 47(7): 186-191.
[3] XIA Chun-yan, WANG Xing-ya, ZHANG Yan. Test Case Prioritization Based on Multi-objective Optimization [J]. Computer Science, 2020, 47(6): 38-43.
[4] SUN Min, CHEN Zhong-xiong, YE Qiao-nan. Workflow Scheduling Strategy Based on HEDSM Under Cloud Environment [J]. Computer Science, 2020, 47(6): 252-259.
[5] WANG Xu-liang, NIE Tie-zheng, TANG Xin-ran, HUANG Ju, LI Di, YAN Ming-sen, LIU Chang. Study on Dynamic Adaptive Caching Strategy for Streaming Data Processing [J]. Computer Science, 2020, 47(11): 122-127.
[6] DONG Ming-gang,LIU Bao,JING Chao. Multi-objective Differential Evolution Algorithm with Fuzzy Adaptive Ranking-based Mutation [J]. Computer Science, 2019, 46(7): 224-232.
[7] WANG Chen-xin, YANG Jia-hai, ZHUANG Yi, LUO Nian-long. Node Resource Scheduling for Future Network Experimentation Facility [J]. Computer Science, 2019, 46(12): 95-100.
[8] ZHAO Yun-tao, CHEN Jing-cheng, LI Wei-gang. Multi-objective Grey Wolf Optimization Hybrid Adaptive Differential Evolution Mechanism [J]. Computer Science, 2019, 46(11A): 83-88.
[9] MA Yuan-feng,LI Ang-ru,YU Hui-min,PAN Xiao-ying. Dynamic Crowding Distance-based Hybrid Immune Algorithm for Multi-objective Optimization Problem [J]. Computer Science, 2018, 45(6A): 63-68.
[10] CHEN Xiang, WANG Qiu-ping. Multi-objective Supervised Defect Prediction Modeling Method Based on Code Changes [J]. Computer Science, 2018, 45(6): 161-165.
[11] LAI Wen-xing, DENG Zhong-min. Improved NSGA2 Algorithm Based on Dominant Strength [J]. Computer Science, 2018, 45(6): 187-192.
[12] WANG Guo-hao, LI Qing-hua and LIU An-feng. Evoluation Genetic Algorithm of Multi-objective Optimization Scheduling on Cloud Workflow [J]. Computer Science, 2018, 45(5): 31-37.
[13] XIONG Li-rong, YOU Ri-jing, JIN Xin. Sensor-based Adaptive Rate Control Method for Mobile Streaming [J]. Computer Science, 2018, 45(10): 124-129.
[14] YAN Hong. Research and Application of Multi-objective Optimization Algorithm Based on Interval Reliability Lower Bound [J]. Computer Science, 2017, 44(Z11): 577-579.
[15] LI Wei-kun, QUE Bo, WANG Wan-liang and NI Li-zhou. Multi-objective Moth-flame Optimization Algorithm Based Optimal Reactive Power Dispatch for Power System [J]. Computer Science, 2017, 44(Z11): 503-509.
Full text



[1] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75 .
[2] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[3] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[4] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[5] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99 .
[6] ZHOU Yan-ping and YE Qiao-lin. L1-norm Distance Based Least Squares Twin Support Vector Machine[J]. Computer Science, 2018, 45(4): 100 -105 .
[7] LIU Bo-yi, TANG Xiang-yan and CHENG Jie-ren. Recognition Method for Corn Borer Based on Templates Matching in Muliple Growth Periods[J]. Computer Science, 2018, 45(4): 106 -111 .
[8] GENG Hai-jun, SHI Xin-gang, WANG Zhi-liang, YIN Xia and YIN Shao-ping. Energy-efficient Intra-domain Routing Algorithm Based on Directed Acyclic Graph[J]. Computer Science, 2018, 45(4): 112 -116 .
[9] CUI Qiong, LI Jian-hua, WANG Hong and NAN Ming-li. Resilience Analysis Model of Networked Command Information System Based on Node Repairability[J]. Computer Science, 2018, 45(4): 117 -121 .
[10] WANG Zhen-chao, HOU Huan-huan and LIAN Rui. Path Optimization Scheme for Restraining Degree of Disorder in CMT[J]. Computer Science, 2018, 45(4): 122 -125 .