A qualitative study of model based approach with the existing approaches for solving combinatorial optimization problems using hybrid strategies

Published Online December 2017 in MECS DOI: 10.5815/ijmecs.2017.12.03

Unlimited numbers of approaches are available to solve combinatorial optimization problems. Some of these approaches employ a single strategy and some others a combination of strategies. Single strategy approach includes the usage of exact, heuristic or metaheuristic algorithm to solve the given problem. Recently researchers have used hybrid strategies, which is nothing but a combination of two or more of these single strategies. An extensive survey on using hybrid metaheuristic strategies to solve combinatorial optimization problems has been made [1]. From this survey, the hybrid meta-heuristic strategies used were classified into simple technique proposal approach, algorithm based approach and framework based approach. When the strategies proposed to solve the problem were not implemented the approach used is simple technique proposal. When these strategies proposed are implemented the approaches used were classified into algorithm based approaches or framework based approaches. These algorithm or framework based approaches were implemented by applying one or more hybrid meta-heuristic [2-10] algorithms.

However, in these approaches used in literature [1] for solving combinatorial optimization problems, less importance is attached to modelling the problem’s solution. By modelling, the problem is broken down into sub-problems. These sub-problems and the relationship that exists between the sub-problems could be depicted in the form of a model. This may enable a better understanding of the problem’s solution and the various parts that constitute this solution. The various parts of the model or solution could then be implemented with different exact, heuristic, meta- heuristic or hybrid meta- heuristic algorithms. Modelling may enable a better comparison between the algorithms implemented for every part of the model, thereby aiding in identifying the best algorithm for this part as well as the best combination of algorithms that form the optimal hybrid strategy.

Therefore, to confirm the importance of modelling and to demonstrate the correctness of the above said theory, a survey, comparison and analysis on using a model based approach has been done in this work and it is organized as follows. Section 2 discusses the related work and Section 3 the motivation behind this work. Section 4 explains what is a model? and Section 5 the various properties achieved by modelling. Section 6 describes a model based approach, compares this approach with the algorithm and framework based approaches and summarizes the findings based on this comparison. Section 7 presents an analysis of the advantages obtained by using model based approach with that of the algorithm and framework based approaches in solving combinatorial problems, using hybrid strategies. Section 8 concludes the paper.

II.    Related Work

Model based approach has been used in a number of domains by different researchers because of the benefits that this approach provides. The benefits claimed by different researchers for using a model based approach are as follows:

• •    A model based systems engineering approach assists in complex system design and documentation process [12]. The benefits of developing conceptual models includes the improvement in the quality of analysis of complex systems, the reduction of costs, design risk, test errors etc. Conceptual models act as a strong base for future analysis, simulation, system requirements definition etc. It promotes component reuse wherever applicable, enables documents traceability and aids in verification and validation.

• •    Model driven engineering aims to create domain models rather than computing concepts. It is stated that models are human understandable description of the system or models present information which can be mechanically analyzed [14]. Models are used particularly to address the structural and compositional aspects during the design phase and model checking and verification in the testing phase. A model-based development is a product development strategy with enhanced completeness, correctness, and precision of information throughout the process [18].

• •    A model based approach uses explicit models to describe the development activities and products [17]. Complexity of the system development is reduced and the understandability of the system is increased, since the design of the system is based

on the existence of explicit models. The main aim of this model-based approach is to produce high quality software at acceptable cost. This is achieved since a model based approach improves both the product and the process that leads to the product.

A model based approach is used in the design of complex systems which are real-time systems, safety critical systems, embedded systems etc. Some examples are as follows: Model-based development to complex and safety-critical aircraft computer systems [18]. A model based approach has also been used to systematically integrate the legacy software components with the embedded control systems and to validate its real-time properties [13]. It is used for online monitoring and diagnosis of a multi agent system where mobile robotic agents provide services [16]. The test bed used is the robo care domain, where robotic agents provide services for the elderly people [16]. It is also applied for a hybrid (Electric/Thermal) propelled unmanned aerial vehicle (HPUAV) project [11]. The information from the real world is converted into models of intention and then into system models in this case.

A model based approach could be used not only to design complex systems but also in planning the process of the complex system development. In this case the development efforts of large scale projects are planned using a model based approach. One way by which this is achieved is by using the work break down structures [15]. A model-based approach is used for project-product planning and this is combined with a project-product lifecycle management which together maintains the links between each subsystem (of the product) and the corresponding project. This facilitates the traceability between the project and the product. As a result a more reliable project plan is created, which reduces the effort required for repeated rework.

Thus, it is clear that a model based approach has been used in a variety of domains [11, 13, 15-19].

III.    Motivation

Combinatorial optimization problems have been solved using a wide variety of hybrid strategies [2-10]. However, the literature reveals that less importance is attached to modelling the problem’s solution while solving combinatorial optimization problems using hybrid strategies [1]. A model based approach may be more beneficial [12, 14, 17, 18], especially when using hybrid strategies to solve a problem, as the problems solution can be depicted in the form of a model and 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. To ensure the correctness of the above statement this work has compared and analyzed the different approaches used to solve combinatorial optimization problems using hybrid strategies and the results have been reported. In order to start exploring the model based approach in detail, the next section starts with an explanation on what is a model.

IV.    Model

A model is a mini representation of a person or an organism or a thing or any proposed structure [20]. In many fields a model is used as a tool for conceptual exploration [21]. In computer science, models are used to describe (software) systems, the elements that constitute this system, their interactions or control and data flows or all of them [24]. Therefore, a model is a kind of system which encompasses one or more elements. The characteristics of each of these elements and the relationship that exists between these elements are clearly depicted in a model and can explicitly be specified as part of the model explanation. Hence, models are highly useful for depicting the solution of the given problem, especially in case of complex problems. In the past, models were mainly used only for documentation purposes but now practises like model driven engineering have increased and influenced their usage through automatic code-generation etc. [24].

V.    Properties Achieved By Modelling

There are a number of properties that can be achieved by modelling any problem or system. The Table 1 below presents the various properties that can be achieved by modelling. It also gives a justifying explanation of how the process of modelling achieves such properties. Besides, these properties have also been classified from three perspectives. They are the architecture perspective, development perspective and quality perspective [39].

Table 1. Properties achieved by Modelling

Perspective	Properties  achieved  by modelling	Explanation
Architecture	Separation of concerns	Since modelling helps in easy decomposition and refinement of problems, modelling helps in the realization of separation of concerns [25, 39].
Architecture	Modularity	By imparting the concept of separation of concerns and by following a systematic and structured development, modelling increases the modularity [33, 39] of a system.
Architecture	Understandability	Conceptual Modelling increases the expressing power of solution representation [42]. Thereby modelling increases the understandability [32-35, 39] of the system, its elements and their relationships.
Architecture	Encapsulation	Modelling encapsulates the design of the solution which is required for further development [26].
Architecture	Manages or    Reduces Complexity	In the software field in order to handle the key issue of software complexity, modelling is the most widely used technique [23, 35, 39]. By increasing the modularity and understandability of the problem and its solution, modelling helps in reducing or managing the complexity.
Development	Customization	Models can be classified into general or problem independent models [29, 30] and specific or problem dependent models [29]. Specific models could be developed from general models; (i.e) a general model is customized with problem specific constraints to form a specific model. Therefore, customization is one notable characteristic of modelling.
Development	Verifiability	Modelling helps in verifying the correctness of the requirements and the feasibility of the system [27, 35, 43].
Development	Intra and Interoperability	Modelling captures the fundamental structure and the relationship between the various elements of the system, thereby depicting the intra and interoperability that exists between the elements of the system. Additionally, modelling also enhances the early intra and interoperability verification between the system elements [27, 35].
Quality	Adaptability	Models easily enable the re-implementation of problems on changing infrastructure [26], thereby enhancing its adaptability.
Quality	Productivity	The productivity of the proposed solution for any specific problem is strongly dependent on both the model and the implementation used to realize the solution [25]. So modelling a problem appropriately and correctly is fundamental and important. Accurate modelling thereby increases the productivity.
Quality	Reliability	Models enhance the reliability of the system as they can be used as tools for system verification and early error detection [27].
Quality	Reusability	Models increase the reusability of the design [39], by producing customized or specific models from generic models. Models also increase the reusability at the implementation level since a model can be used as a base from which several different implementations could be realized.
Quality	Improved overall quality	Therefore, since modelling brings an improvement in all the above mentioned properties the overall quality of the problem depiction and solution representation is also increased [39].

VI.    Model Based Approach

A model based approach encourages the use of explicit models or diagrams to explain and describe the various elements of the system and their relationships [22]. For example these elements may be the phases or activities of a process or parts of a product etc. Since a model based approach supports the above said properties as mentioned in the previous section it seems to be useful in solving complex problems [23, 25-27, 32-35, 39]. However, a comparison between the algorithm or technique based approach, framework based approach and the model based approach has been done with regard to the functional and non-functional aspects and this has been presented in the Table 2 below. This comparison between the approaches is made in order to understand the approaches clearly and the difference between the approaches better.

Table 2. Comparison between algorithm or technique based approach, framework based approach and model based approach

Functional /Non-Functional aspect	Algorithm or technique based approach	Framework based approach	Model based approach
Functional aspect Pictorial representation    of functionality	This approach gives a pictorial representation of the problem’s solution at implementation level only [41].	This approach gives a pictorial representation of the problem’s solution at implementation level only.	This approach gives a pictorial representation of the problem’s solution at design level [40].
Functional aspect Functional Dependency	An algorithm or a technique is a step by step procedure used to understand the solution to a problem [37] in an accurate and orderly manner. Therefore this approach is problem or technique dependent.	A framework consists of software libraries with reusable code wrapped in the form of an application programming interface (API) which brings several different components together to enable development of a project or solution [28]. Therefore a framework based approach is limited by the algorithms or techniques implemented as API in the framework to solve a particular problem.	Models can be designed in a problem dependent specific manner [29] or problem independent generic manner [29, 30].
Functional aspect Level of abstraction	Since algorithm is a step by step approach to solve a problem, an algorithm based approach is a low level approach that gives a picture of the solution at implementation level only [36].	In a framework based approach specific API’s from the framework libraries are combined to solve a problem [28]. Therefore, this approach is a low level approach that gives a picture of the solution at implementation level only.	The level of abstract representation of a system is high in case of a model based approach [31]. This is because it gives a high level knowledge about the design of the problem or system and its elements.
Non-Functional aspect Applicability	Could be used for solving simple problems. Designing solutions of complex problems using this approach could be difficult although it is possible to do so [35].	Could be used to implement specific simple and complex problems only, which is limited to the API’s available in the framework [28].	Could be used to design the solution of any simple or complex problem [34, 35]. Complex problems are thereby designed into many simple problems.
Non-Functional aspect Understandability	It is difficult to understand the solution to a given complex problem when solved using this approach, as no proper modelling or designing of the solution has been done [35].	It is difficult to understand the solution to a given complex problem when solved using this approach [35].	Model based approaches increases the understanding of complex problems [32, 35], as they allow systematic and structured, decomposition and refinement of the problem in a simple manner. Thereby a model based approach increases the modularity [33], understandability [32-35, 39, 42] and reduces the complexity of problems.
Non-Functional aspect Reusability	Reuse of the same algorithm or technique without any modification for different problems is possible.	Reuse of some algorithm or technique employed within the framework for solving different problems is possible [28].	A model could be reused at both design level as well as implementation level. At design level generic models are reused with problem specific constraints to obtain specific models. At implementation level reuse is possible by implementing several algorithms or frameworks to solve every part of the model [30, 32]. Therefore, a model based approach enables reusability at both design and implementation level.
Non-Functional aspect Verifiability     and Reliability	An algorithm or technique based approach may increase the verifiability and reliability of the system at the implementation or technique level only [36].	This approach may increase the verifiability and reliability of the system at the implementation level only.	Model based approach aids in increasing the verifiability [34, 35] and reliability [33, 34] of the system at design level [43] thereby improving the overall quality of the solution.

• A. Findings Based On Comparison Between The Approaches

A model based approach gives clear understanding of the solution to complex problems by providing a pictorial representation at design level, thereby having a high level of abstraction. By using a model based approach the solution representation is easily understandable, reusable, verifiable and reliable. A model can be designed in a problem dependent or independent manner. Algorithm and framework based approaches are problem dependant and provides a low level of abstraction of the problems solution. Algorithm as well as framework based approaches have limited applicability and understandability. Reusability, reliability and verifiability are at implementation level only for both the approaches. Both these approaches do not include solution representation from an architecture perspective, as in the case of model based approach. This is clearly visible from the Table 2 above as well as depicted pictorially in the Fig.1, Fig.2 and Fig.3 below.

Therefore, the usage of a model based approach is more beneficial for solving complex combinatorial optimization problems as it helps in depicting the solution for the problem from an architectural perspective, making the solution easily understandable, reusable, verifiable and reliable. When many different hybrid approaches are used to solve the same problem, this architectural perspective conveniently portrays the combination of techniques used in each of these hybrid approaches. Further, when a 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 problem in an optimal manner.

Fig.2. Aspects addressed by a Framework based approach

Fig.3. Aspects addressed by a Model based approach

Fig.1. Aspects addressed by an Algorithm or Technique based approach

VII.    Analysis of the Advantages Obtained by Using Model based Approach

To finally analyse the need for a model based approach in solving combinatorial optimization problems especially using hybrid strategies, an additional comparison is made on the basis of the various properties achieved by modelling, between the model based approach with that of the algorithm and framework based approaches used in literature to solve different combinatorial optimization problems using hybrid metaheuristic strategies. For this, an extensive survey on using hybrid meta-heuristic approaches for solving combinatorial optimization problems [1] has been made and a few important papers were selected from this survey for the comparison. This is depicted in the Table 3 below. If a particular property achieved by modelling is not possessed by the approach then a ‘--’ is present in the corresponding column. If a property is possessed by the approach only at implementation level and if it is a weak possession then this is marked by using ‘+-’, if it is a moderate possession then this is marked by using ‘+’. If a particular property is possessed by the approach at design level then it is marked as ‘++’.

On analysing the Table 3 below, properties such as separation of concerns [5, 7], modularity [3-5, 8-10], understandability [3-5,8-10] are possessed by the algorithm and framework based approaches in a weak manner at implementation level. Properties such as customisation [5, 7], verifiability [3-5, 8-10], reliability [3-5, 7-10] and reusability [5,7] are possessed by the algorithm and framework based approaches in a moderate manner at implementation level. Intra and interoperability is possessed by all the approaches either in a moderate manner at implementation level [3-6, 8-10] or at design level [7, 38].

It is clear from the Table 3 below that the algorithm based approach and framework based approach does not exhibit some of the properties of modelling and exhibit a few other properties predominantly at an implementation level. Since the model based approach used enables the appropriate modelling of a given problem [38] it possesses all the properties at a design level when compared to the other approaches. Therefore, it is obvious from table 3 that the model based approach achieves properties such as generality (customization), separation of concerns, modularity, understandability, adaptability, encapsulation, reduces complexity, increases productivity, verifiability, reliability, reusability, intra and interoperability, thereby increasing the overall quality of the solution representation.

Therefore, to represent and solve complex combinatorial optimization problems in general and especially using hybrid strategies a model based approach is useful. As each part of the model could be implemented with many different strategies, in order to increase the clarity of which is an optimal strategy for every part of the model, to identify the optimal combination of strategies or the optimal hybrid strategy, realized and implemented to solve a given problem and to make a statistical assessment of the results produced by these hybrid approaches, a model based approach is appropriate.

Table 3. Comparison of the proposed model based approach with the algorithm and framework based approaches used in literature

Properties achieved by modelling	[3]/ Two-phase hybrid algorithm for vehicle routing problem with time windows	[4]/ Hybrid meta heuristics algorithms for task assignment in heterogene ous computing systems	[5]/ A Framework for Hybrid Meta heuristics for Generalized Network Design Problems	[6]/ Algorith m for the mobile mapping van problem	[7]/Hybrid Metaheuristic Framewor ks      :A Functional Approach	[8]/ GELS-GA: Hybrid Meta heuristic Algorith m for Solving Multiple Travellin g Salesman Problem	[9]/ Hybrid Meta heuristic Algorith m for the Clustere d Vehicle Routing Problem	[10]/ A Bicriteria hybrid meta heuristic algorithm for analyzing an integrated automotive supply chain	[38]/ web service selection/ composition model
Separation of concerns	—	--	+-	--	+-	--	--	--	++
Modularity	+-	+-	+-	—	—	+-	+-	+-	++
Understandabi lity	+-	+-	+-	--	--	+-	+-	+-	++
Encapsulation	--	--	--	--	--	--	--	--	++
Manages or Reduces Complexity	--	--	--	--	--	--	--	--	++
Customization	--	--	+	--	+	--	--	--	++
Verifiability	+	+	+	—	—	+	+	+	++
Intra and Interoperabilit y	+	+	+	+	++	+	+	+	++
Adaptability	--	--	--	--	--	--	--	--	++
Productivity	--	--	--	--	--	--	--	--	++
Reliability	+	+	+	—	+	+	+	+	++
Reusability	--	--	+	--	+	--	--	--	++

VIII.    Conclusion

In order to understand the significance of using a model based approach, a survey on model based approach and the properties achieved by modelling are done. To understand the differences between the approaches used in literature, a comparison of the model based approach with the algorithm or technique, and framework based approaches is presented. The survey and comparison ascertains that modelling enables a better understanding of the problem’s solution as well as the various parts that constitute the solution. In addition, it is clear that modelling establishes properties such as customisation, separation of concerns, modularity, understandability, adaptability, encapsulation, reduces complexity, increases productivity, verifiability, reliability, reusability, intra and interoperability, thereby increasing the overall quality of the problem’s solution representation.

An analysis of the advantages obtained by using model based approach with that of the algorithm and framework based approaches in solving the combinatorial optimization problems using hybrid strategies is presented. This analysis highlights that the model based approach is useful when compared to the algorithm or technique and framework based approaches in solving the combinatorial optimization problems using hybrid strategies as it suitably portrays the different hybrid strategies used to solve the same problem from an architectural perspective, aiding in identifying the best strategy for every part of the model and the optimal hybrid strategy for the entire problem.