Now showing 1 - 10 of 12
No Thumbnail Available
Publication

A Hybrid Algorithm for Multi-objective Test Case Selection

2018-10-04, Saber, Takfarinas, Delavernhe, Florian, Papadakis, Mike, O'Neill, Michael, Ventresque, Anthony

Testing is crucial to ensure the quality of software systems-but testing is an expensive process, so test managers try to minimise the set of tests to run to save computing resources and speed up the testing process and analysis. One problem is that there are different perspectives on what is a good test and it is usually not possible to compare these dimensions. This is a perfect example of a multi-objective optimisation problem, which is hard-especially given the scale of the search space here. In this paper, we propose a novel hybrid algorithm to address this problem. Our method is composed of three steps: a greedy algorithm to find quickly some good solutions, a genetic algorithm to increase the search space covered and a local search algorithm to refine the solutions. We demonstrate through a large scale empirical evaluation that our method is more reliable (better whatever the time budget) and more robust (better whatever the number of dimensions considered)-in the scenario with 4 objectives and a default execution time, we are 178% better in hypervolume on average than the state-of-the-art algorithms.

No Thumbnail Available
Publication

Preliminary Study of Multi-objective Features Selection for Evolving Software Product Lines

2016-09-24, Brevet, David, Saber, Takfarinas, Botterweck, Goetz, Ventresque, Anthony

When dealing with software-intensive systems, it is often beneficial to consider families of similar systems together. A common task is then to identify the particular product that best fulfils a given set of desired product properties. Software Product Lines Engineering (SPLE) provides techniques to design, implement and evolve families of similar systems in a systematic fashion, with variability choices explicitly represented, e.g., as Feature Models. The problem of picking the 'best' product then becomes a question of optimising the Feature Configuration. When considering multiple properties at the same time, we have to deal with multi-objective optimisation, which is even more challenging. While change and evolution of software systems is the common case, to the best of our knowledge there has been no evaluation of the problem of multi-objective optimisation of evolving Software Product Lines. In this paper we present a benchmark of large scale evolving Feature Models and we study the behaviour of the state-of-the-art algorithm (SATIBEA). In particular, we show that we can improve both the execution time and the quality of SATIBEA by feeding it with the previous configurations: our solution converges nearly 10 times faster and gets an 113% improvement after one generation of genetic algorithm.

No Thumbnail Available
Publication

Multi-objective Virtual Machine Reassignment for Large Data Centres

2017, Saber, Takfarinas

Data centres are large IT facilities composed of an intricate collection of interconnected and virtualised computers, connected services, and complex service-level agreements. Optimising data centres, often attempted by reassigning virtual machines to servers, is both desirable and challenging. It is desirable as it could save a large amount of money: using servers better would lead to decommissioning unused ones and organising services better would increase reliability and maintenance. It is also challenging as the search space is very large and very constrained, which makes the solutions difficult to find. Moreover, in practice assignments can be evaluated from different perspectives, such as electricity cost, overall reliability, migration overhead and cloud cost. Managers in data centres then make complex decisions and need to manipulate possible solutions favouring different objectives to find the right balance. Another element I consider in the context of this work is that organisations hosting large IT facilities are often geographically distributed – which means these organisations are composed of a number of hosting departments which have different preferences on what to host and where to host it, and a certain degree of autonomy. The problem is even more challenging as companies can now choose from a pool of public cloud services to host some of their virtual machines.In this thesis, I address the problem of multi-objective virtual machine (VM) reassignment for large data centres from three realistic and challenging perspectives.• First, I demonstrate how intractable is the exact resolution of the problem in a centralised context: I perform a thorough performance evaluation of classical solvers and metaheuristics, and I propose a novel hybrid algorithm which outperforms them.• Second, I design a two-level system addressing multi-objective VM reassignment for large decentralised data centres. My system takes care of both the reassignment of VMs and their placement within the hosting departments and I propose algorithms that optimise each of the levels.• Third, I extend my work to the hybrid cloud world – i.e., when companies can decide to use their own internal resources or pay for public clouds computing resources. The problem becomes now more dynamic (as prices evolve) and challenging, and I propose a novel algorithm that takes all these elements into account.

No Thumbnail Available
Publication

MILP for the Multi-objective VM Reassignment Problem

2015-11-11, Saber, Takfarinas, Ventresque, Anthony, Marques-Silva, Joao, Thorburn, James, Murphy, Liam, B.E.

Machine Reassignment is a challenging problem for constraint programming (CP) and mixed integer linear pro- gramming (MILP) approaches, especially given the size of data centres. The multi-objective version of the Machine Reassignment Problem is even more challenging and it seems unlikely for CP or MILP to obtain good results in this context. As a result, the first approaches to address this problem have been based on other optimisation methods, including metaheuristics. In this paper we study under which conditions a mixed integer optimisation solver, such as IBM ILOG CPLEX, can be used for the Multi-objective Machine Reassignment Problem. We show that it is useful only for small or medium scale data centres and with some relaxations, such as an optimality tolerance gap and a limited number of directions explored in the search space. Building on this study, we also investigate a hybrid approach, feeding a metaheuristic with the results of CPLEX, and we show that the gains are important in terms of quality of the set of Pareto solutions (+126.9% against the metaheuristic alone and +17.8% against CPLEX alone) and number of solutions (8.9 times more than CPLEX), while the processing time increases only by 6% in comparison to CPLEX for execution times larger than 100 seconds.

No Thumbnail Available
Publication

Towards a Multi-Objective VM Reassignment for Large Decentralised Data Centres

2015-12-10, Saber, Takfarinas, Ventresque, Anthony, Brandic, Ivona, Thorburn, James, Murphy, Liam, B.E.

Optimising the IT infrastructure of large, often geographically distributed, organisations goes beyond the classical virtual machine reassignment problem, for two reasons: (i) the data centres of these organisations are composed of a number of hosting departments which have different preferences on what to host and where to host it; (ii) the top-level managers in these data centres make complex decisions and need to manipulate possible solutions favouring different objectives to find the right balance. This challenge has not yet been comprehensively addressed in the literature and in this paper we demonstrate that a multi-objective VM reassignment is feasible for large decentralised data centres. We show on a realistic data set that our solution outperforms other classical multi-objective algorithms for VM reassignment in terms of quantity of solutions (by about 15% on average) and quality of the solutions set (by over 6% on average). 

No Thumbnail Available
Publication

Exact and Hybrid Solutions for the Multi-objective VM Reassignment Problem

2017-02-23, Saber, Takfarinas, Marques-Silva, Joao, Thorburn, James, Ventresque, Anthony

Machine Reassignment is a challenging problem for constraint programming (CP) and mixed integer linear programming (MILP) approaches, especially given the size of data centres. Hybrid solutions mixing CP and heuristic algorithms, such as, large neighbourhood search (CBLNS), also struggle to address the problem given its size and number of constraints. The multi-objective version of the Machine Reassignment Problem is even more challenging and it seems unlikely for CP, MILP or hybrid solutions to obtain good results in this context. As a result, the first approaches to address this problem have been based on other optimisation methods, including metaheuristics. In this paper we study three things: (i) under which conditions a mixed integer optimisation solver, such as IBM ILOG CPLEX, can be used for the Multi-objective Machine Reassignment Problem; (ii) how much of the search space can a well-known hybrid method such as CBLNS explore; and (iii) can we find a better hybrid approach combining MILP or CBLNS and another recent metaheuristic proposed for the problem (GeNePi). We show that MILP can handle only small or medium scale data centres, and with some relaxations, such as, an optimality tolerance gap and a limited number of directions explored in the search space. CBLNS on the other hand struggles with the problem in general but achieves reasonable performance for large instances of the problem. However, we show that our hybridisation improves both the quality of the set of solutions (CPLEX+GeNePi and CBLNS+GeNePi improve the solutions by +17.8% against CPLEX alone and +615% against CBLNS alone) and number of solutions (8.9 times more solutions than CPLEX alone and 56.76 times more solutions than CBLNS alone), while the processing time of CPLEX+GeNePi and CBLNS+GeNePi increases only by 6% and 16.4% respectively. Overall, the study shows that CPLEX+GeNePi is the best algorithm for small instances (CBLNS+GeNePi only gets 45.2% of CPLEX+GeNePi’s hypervolume) while CBLNS+GeNePi is better than the others on large instances (that CPLEX+GeNePi cannot address).

No Thumbnail Available
Publication

Is seeding a good strategy in multi-objective feature selection when feature models evolve?

2018-03, Saber, Takfarinas, Brevet, David, Botterweck, Goetz, Ventresque, Anthony

Context: When software architects or engineers are given a list of all the features and their interactions (i.e., a Feature Model or FM) together with stakeholders 'preferences' their task is to find a set of potential products to suggest the decision makers. Software Product Lines Engineering (SPLE) consists in optimising those large and highly constrained search spaces according to multiple objectives reflecting the preference of the different stakeholders. SPLE is known to be extremely skill- and labour-intensive and it has been a popular topic of research in the past years.Objective: This paper presents the first thorough description and evaluation of the related problem of evolving software product lines. While change and evolution of software systems is the common case in the industry, to the best of our knowledge this element has been overlooked in the literature. In particular, we evaluate whether seeding previous solutions to genetic algorithms (that work well on the general problem) would help them to find better/faster solutions.Method: We describe in this paper a benchmark of large scale evolving FMs, consisting of 5 popular FMs and their evolutions – synthetically generated following an experimental study of FM evolution. We then study the performance of a state-of-the-art algorithm for multi-objective FM selection (SATIBEA) when seeded with former solutions.Results: Our experiments show that we can improve both the execution time and the quality of SATIBEA by feeding it with previous configurations. In particular, SATIBEA with seeds proves to converge an order of magnitude faster than SATIBEA alone.Conclusion: We show in this paper that evolution of FMs is not a trivial task and that seeding previous solutions can be used as a first step in the optimisation - unless the difference between former and current FMs is high, where seeding has a limited impact.

No Thumbnail Available
Publication

A comparative study of multi-objective machine reassignment algorithms for data centres

2019-09-20, Saber, Takfarinas, Gandibleux, Xavier, O'Neill, Michael, Murphy, Liam, B.E., Ventresque, Anthony

At a high level, data centres are large IT facilities hosting physical machines (servers) that often run a large number of virtual machines (VMs)— but at a lower level, data centres are an intricate collection of interconnected and virtualised computers, connected services, complex service-level agreements. While data centre managers know that reassigning VMs to the servers that would best serve them and also minimise some cost for the company can potentially save a lot of money—the search space is large and constrained, and the decision complicated as they involve different dimensions. This paper consists of a comparative study of heuristics and exact algorithms for the Multi-objective Machine Reassignment problem. Given the common intuition that the problem is too complicated for exact resolutions, all previous works have focused on various (meta)heuristics such as First-Fit, GRASP, NSGA-II or PLS. In this paper, we show that the state-of-art solution to the single objective formulation of the problem (CBLNS) and the classical multi-objective solutions fail to bridge the gap between the number, quality and variety of solutions. Hybrid metaheuristics, on the other hand, have proven to be more effective and efficient to address the problem – but as there has never been any study of an exact resolution, it was difficult to qualify their results. In this paper, we present the most relevant techniques used to address the problem, and we compare them to an exact resolution ( -Constraints). We show that the problem is indeed large and constrained (we ran our algorithm for 30 days on a powerful node of a supercomputer and did not get the final solution for most instances of our problem) but that a metaheuristic (GeNePi) obtains acceptable results: more (+188%) solutions than the exact resolution and a little more than half (52%) the hypervolume (measure of quality of the solution set).

No Thumbnail Available
Publication

VM reassignment in hybrid clouds for large decentralised companies: A multi-objective challenge

2017, Saber, Takfarinas, Thorburn, James, Murphy, Liam, B.E., Ventresque, Anthony

Optimising the data centres of large IT organisations is complex as (i) they are composed of various hosting departments with their own preferences and (ii) reassignment solutions can be evaluated from various independent dimensions. But in reality, the problem is even more challenging as companies can now choose from a pool of cloud services to host some of their workloads. This hybrid search space seems intractable, as each workload placement decision (seen as running in a virtual machine on a server) is required to answer many questions: can we host it internally? In which hosting department? Are the capital allocators of this hosting department ok with this placement? How much does it save us and is it safe? Is there a better option in the Cloud? Etc. In this paper, we define the multi-objective VM reassignment problem for hybrid and decentralised data centres. We also propose H2¿D2, a solution that uses a multi-layer architecture and a metaheuristic algorithm to suggest reassignment solutions that are evaluated by the various hosting departments (according to their preferences). We compare H2¿D2 against state-of-the-art multi-objective algorithms and find that H2¿D2 outperforms them both in terms of quantity (approx 30% more than the second-best algorithm on average) and quality of solutions (19% better than the second-best on average).

No Thumbnail Available
Publication

ROThAr: Real-time On-line Traffic Assignment with Load Estimation

2013-11-01, Saber, Takfarinas, Ventresque, Anthony, Murphy, John

More and more drivers use on-board units to help them navigate in the increasing urbanised environment they live and work in. These system (e.g., routing applications on smart phones) are now very often on-line, and use information from the traffic situation (e.g., accidents, congestion) to get the best route. We can now envisage a world where all trips are assigned and updated by such an on-line system, making the best routing decisions based on traffic conditions. The problem is that current systems consider only 'local' elements (e.g., driver preference and current traffic condition) and do not make routing decisions from a global perspective. This can lead to a lot of similar routing assignments that could lead to further traffic congestion. The objective of the next generation on-line navigation systems is then to come up with a 'smart', real-time route assignment, which balances the load between the different road segments and offers the best quality to the drivers. However, every routing decision made has an impact on the traffic conditions (one more vehicle on the road segments selected) and computing the load induced by the trips is a computationally heavy problem. This paper addresses this question of real-time on-line traffic assignment, and shows that under certain conditions it is possible to have (i) an accurate estimation of the load and travel time on every road segment and (ii) an optimised traffic assignment that adapts to divergence and evolutions (e.g., accidents) of the system.