A Qualitative Study of Model based Approach with the Existing Approaches for Solving Combinatorial Optimization Problems Using Hybrid Strategies

Full Text (PDF, 579KB), PP.17-25

Views: 0 Downloads: 0


Sangeetha Muthuraman 1,* V. Prasanna Venkatesan 2

1. Department of Computer Science and Engineering, Manonmaniam Sundaranar University, 14, V.O.C. Street, Kamaraj Nagar, Puducherry – 605011, 00918903586378

2. Department of Banking Technology, School of Management, Pondicherry University, Kalapet, Puducherry – 605014, 00919486199939

* Corresponding author.

DOI: https://doi.org/10.5815/ijmecs.2017.12.03

Received: 22 Sep. 2017 / Revised: 26 Oct. 2017 / Accepted: 8 Nov. 2017 / Published: 8 Dec. 2017

Index Terms

Model based approach, Solving combinatorial optimization problems, Hybrid strategies


In literature, combinatorial optimization problems have been solved using several hybrid strategies. From the principles of software engineering, it is explicit that modelling enables better understanding of the problem’s solution as well as the various parts that constitute the solution. However, the literature reveals that there is less importance attached to modelling the problem’s solution while solving combinatorial optimization problems using hybrid strategies. Therefore, in order to better understand the advantages and significance of using a model based approach in solving such problems, a survey on model based approach and the various properties achieved by modelling has been carried out. A comparison of the algorithm or technique based approach, framework based approach and model based approach is done to better understand the differences between the approaches and their outcomes. From the comparison made between the approaches and the analysis made on the advantages of using a model based approach in solving combinatorial optimization problems using hybrid strategies, it is found that a model based approach gives clear and better understanding of complex problems by making their representation easily modular, understandable, adaptable, verifiable, reliable, customizable, reusable etc. Further, when hybrid strategies are used, and the problems solution is depicted in the form of a model, every part of the model could be implemented using different algorithms and frameworks, thus aiding to identify the optimal algorithm or framework for every part of the model, as well as the most efficient hybrid combination that solves the whole problem in an optimal manner.

Cite This Paper

Sangeetha Muthuraman, V. Prasanna Venkatesan, "A Qualitative Study of Model based Approach with the Existing Approaches for Solving Combinatorial Optimization Problems Using Hybrid Strategies", International Journal of Modern Education and Computer Science(IJMECS), Vol.9, No.12, pp. 17-25, 2017. DOI:10.5815/ijmecs.2017.12.03


[1]Sangeetha Muthuraman and Prasanna Venkatesan, “A comprehensive study on hybrid meta-heuristic approaches used for solving combinatorial optimization problems,” IEEE Xplore 2016 World Congress on Computing and Communication Technologies (WCCCT 2016), p. 185-200, December 2016, DOI 10.1109/WCCCT.2016.53.
[2]G¨unther R. Raidl and Jakob Puchinger, “Combining (integer) linear programming techniques and metaheuristics for combinatorial optimization,” Hybrid Metaheuristics Volume 114 of the series Studies in Computational Intelligence, pp. 31-62, 2008.
[3]Jorg Homberger and Hermann Gehring, “A two-phase hybrid metaheuristic for the vehicle routing problem with time windows,” European Journal of Operational Research, vol. 162, pp.220–238, 2005.
[4]Sancho Salcedo-Sanz,Yong Xub and XinYao, “Hybrid meta-heuristics algorithms for task assignment in heterogeneous computing systems,” Journal of Computers and Operations Research, vol. 33, pp.820–835, 2006.
[5]Bin Hu, “Hybrid metaheuristics for generalized network design problems,” Ph.d thesis, Vienna University of technology, 2008. https://www.ac.tuwien.ac.at/files/pub/hu_08.pdf [Accessed 1 September 2015].
[6]Pieter Vansteenwegen, Wouter Souffriau and Kenneth S¨orensen, “Solving the mobile mapping van problem: a hybrid metaheuristic for capacitated arcrouting with soft time windows,” Journal of Computers and Operations Research, vol. 37 no. 11, pp.1870-1876, 2010.
[7]Richard James Senington, “Hybrid meta-heuristic frameworks: a functional approach,” Ph.d thesis, The University of Leeds School of Computing, 2013, etheses.whiterose.ac.uk/4847/1/Richard%20Senington's%20thesis.pdf
[8]Ali A. R. Hosseinabadi, Maryam Kardgar, Mohammad Shojafar, Shahaboddin Shamshirband and Ajith Abraham, “GELS-GA: Hybrid metaheuristic algorithm for solving multiple travelling salesman problem,” 14th International Conference on Intelligent Systems Design and Applications (ISDA), p. 76-81, 2014.
[9]Thibaut Vidal, Maria Battarra, Anand Subramanian and Gunes Erdogan, “Hybrid metaheuristics for the clustered vehicle routing problem,” Journal of Computers and Operations Research, vol. 58 no. C, pp. 87-99, 2015. http://arxiv.org/pdf/1404.6696.pdf
[10]Sherif A Masoud and Scott J Mason, “A bi-criteria hybrid metaheuristic for analysing an integrated automotive supply chain,” Journal of the Operational Research Society, vol. 67 no. 3, pp. 516-526, 2015.
[11]Retho Fabien, Smaoui Hichem, Vannier Jean-Claude and Dessante Philippe, “A model-based method to support complex system design via systems interactions analysis,” Posters Workshop at CSD&M 2013, p. 115-126, 2013.
[12]J. Stephen Topper and Nathaniel C. Horner, “Model-based systems engineering in support of complex systems development,” Johns Hopkins APL technical digest, vol. 32 no. 1, pp. 419-432, 2013.
[13]Josip Babi´c, “Model-based approach to real-time embedded control systems development with legacy components integration,” Ph.d thesis, Department of electrical engineering and computing, University of Zagreb, 2014.
[14]N Md Jubair Basha, Salman Abdul Moiz and Mohammed Rizwanullah, “Model based software development: issues & challenges,” Special Issue of International Journal of Computer Science & Informatics (IJCSI), ISSN (PRINT): vol. II no. 1, 2, pp. 2231–5292, Mar. 6 2012, https://arxiv.org/pdf/1203.1314
[15]Amira Sharon and Dov Dori, “A model-based approach for planning work breakdown structures of complex systems projects,” 14th IFAC Symposium on Information Control Problems in Manufacturing, vol. 45 no. 6, p. 1083-1088, May 2012.
[16]R. Micalizio, P. Torasso and G. Torta, “On-line monitoring and diagnosis of multi-agent systems: a model based approach,” 16th Eureopean Conference on Artificial Intelligence, ECAI'2004, including Prestigious Applicants of Intelligent Systems, PAIS 2004, Valencia, Spain, August 22-27, 2004.
[17]B. Sch¨atz, A. Pretschner, F. Huber, and J. Philipps, “Model-based development of embedded systems,” https://www4.in.tum.de/~schaetz/papers/SchaetzPretschnerHuberPhillips.pdf
[18]Wilfredo Torres-Pomales, “Is model-based development a favorable approach for complex and safety-critical computer systems on commercial aircraft?,” National Aeronautics and Space Administration Langley Research Center, Hampton, Virginia, December 2014.
[19]Qian Chen, Sherif Abdelwahed and Abdelkarim Erradi, “A model-based validated autonomic approach to self-protect computing systems”, Journal of IEEE Internet of Things, vol. 1, no. 5, pp. 446 – 460, Oct. 2014 .
[20]Google dictionary, Model, https://www.google.co.in/?gfe_rd=cr&ei=dRi7Ve_WDLLv8wey07CQBA#q=what+is+a+model [Accessed 1 September 2015].
[21]Kevin A. Clarke and David M. Primo, “A model-based approach,” Journal of Modernizing Political Science, vol. 5 no. 4, pp. 741-753, 2007. https://rochester.edu/college/psc/clarke/POPArticle.pdf
[22]Bernhard Schaetz, Alexander Pretschner, Franz Huber and Jan Philipps, “Model-based development,” Habilitation Thesis, Institut f¨ur Informatik der , Technische Universität München, 2002 , https://www4.in.tum.de/~schaetz/papers/TUM-I0402.pdf [Accessed 1 September 2015].
[23]Birgit Vogel-Heuser, Daniel Schütz, Timo Frank and Christoph Legat, “Model-driven engineering of manufacturing automation software projects – A SysML-based approach,” Journal of Mechatronics, vol. 24, pp. 883–897, 2014, http://www.sciencedirect.com/science/article/pii/S0957415814000853
[24]Christian Saad, Florian Lautenbacher and Bernhard Bauer, “An attribute-based approach to the analysis of model characteristics,” 1st International workshop on Future Trends of Model-Driven Development, Milan, Italy, p. 13-22, 2009, https://www.informatik.uni-augsburg.de/lehrstuehle/swt/vs/publikationen/veroeffentlichungen/2009_ICEIS/AttributeBasedModelAnalysis.pdf
[25]Andrzej Jodłowski, Piotr Habela, Jacek Płodzien and Kazimierz Subieta, “Extending OO metamodels towards dynamic object roles,” On The Move to Meaningful Internet Systems 2003: CoopIS, DOA, and ODBASE Volume 2888 of the series LNCS, pp. 1032-1047, 2003.
[26]Richard Soley, “Model driven architecture: three years on,” On The Move to Meaningful Internet Systems 2003: CoopIS, DOA, and ODBASE Volume 2888 of the series LNCS, pp. 1048-1049, 2003.
[27]NDIA Systems Engineering Division M&S Committee, Final report of the model based engineering (MBE) subcommittee, national defence industry association, 10 February 2011 http://www.ndia.org/Divisions/Divisions/SystemsEngineering/Documents/Committees/M_S%20Committee/Reports/MBE_Final_Report
_Document_(2011-04-22)_Marked_Final_Draft.pdf (Accessed 1 September 2015).
[28]stack overflow, “what is a software framework,” http://stackoverflow.com/questions/2964140/what-is-a-software-framework [Accessed 1 September 2015].
[29]David E. Thompson, “Design analysis: mathematical modeling of nonlinear systems,” 1999, https://books.google.co.in/books?isbn=0521621704 [Accessed 1 September 2015].
[30]Helmar Burkhart, CONPAR 90 - VAPP IV: Joint International Conference on Vector and Parallel ..., 1990, https://books.google.co.in/books?isbn=3540530657 isbn:3540530657, [Accessed 1 September 2015].
[31]Intentional Software Corp., “Appropriate levels of abstraction,” http://www.intentsoft.com/appropriate_lev-2/ [Accessed 1 September 2015].
[32]No Magic, “Modeling benefits,” http://www.nomagic.com/getting-started/modeling-benefits.html, [Accessed 1 September 2015].
[33]Jordi Cabot, “List of the (supposed) benefits of software modelling,” http://modeling-languages.com/list-supposed-benefits-software-modeling/, [Accessed 1 September 2015].
[34]ISTQB exam certification, “What is prototype model – advantages, disadvantages and when to use it,” http://istqbexamcertification.com/what-is-prototype-model-advantages-disadvantages-and-when-to-use-it/, [Accessed 1 September 2015].
[35]Grady Booch, James Rumbaugh and Ivar Jacobson, The Unified Modeling Language User Guide, 2nd ed., Addison Wesley Professional, 2005, http://icourse.cuc.edu.cn/networkprogramming/resources/Book_UML/The%20Unified%20Modeling%20Language%20User%20Guide
%20-%20Second%20Edition.pdf, [Accessed 1 September 2015].
[36]Programiz, “Algorithm in programming”, http://www.programiz.com/article/algorithm-programming, [Accessed 1 September 2015].
[37]Ellis Horowitz, Sartaj Sahni and Sanguthevar Rajasekaran, Fundamentals of Computer Algorithms, second edition Universities Press (India) Private Limited, 2008.
[38]Sangeetha Muthuraman and Prasanna Venkatesan, “Design of QOS based web service selection/composition hyper-heuristic model,” International Conference on Informatics and analytics (ICIA'16), 2016, ISBN: 978-1-4503-4756-3.
[39]Roger S. Pressman, Software Engineering: A Practitioner’s Approach, 7/e McGraw-Hill, 2009.
[40]Wikipedia, “Conceptual model,” https://en.wikipedia.org/wiki/Conceptual_model, [Accessed 13 October 2016].
[41]Wikipedia, “Flowchart,” https://en.wikipedia.org/wiki/Flowchart, [Accessed 13 October 2016].
[42]Pankaj Jalote, A Concise Introduction to Software Engineering, Springer Science+Business Media, Springer-Verlag London Limited, 2008, DOI: 10.1007/978-1-84800-302-6.
[43]Alfredo Garro and Andrea Tundis, “A model-based method for system reliability analysis,” 2012 Symposium on Theory of Modeling and Simulation - DEVS Integrative M&S Symposium Article No. 2, Orlando, Florida — March 26 - 30, 2012 ISBN: 978-1-61839-786-7.