Exact and Hybrid Solutions for the Multi-objective VM Reassignment Problem
Files in This Item:
|CPLEX_for_MOMRP_IJTAI_v1_BlackWhite_v2.pdf||1.5 MB||Adobe PDF||Download|
|Title:||Exact and Hybrid Solutions for the Multi-objective VM Reassignment Problem||Authors:||Saber, Takfarinas; Marques-Silva, Joao; Thorburn, James; Ventresque, Anthony||Permanent link:||http://hdl.handle.net/10197/8417||Date:||23-Feb-2017||Online since:||2018-02-01T02:00:14Z||Abstract:||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).||Funding Details:||Science Foundation Ireland||metadata.dc.description.othersponsorship:||Lero||Type of material:||Journal Article||Publisher:||World Scientific Publishing||Journal:||International Journal on Artificial Intelligence Tools||Volume:||26||Issue:||1||Copyright (published version):||2017 World Scientific Publishing Company||Keywords:||Multi-objective optimisation; VM/Machine reassignment; Mixed integer linear programming; Large neighbourhood search; Hybrid-metaheuristics||DOI:||10.1142/S0218213017600041||Language:||en||Status of Item:||Peer reviewed|
|Appears in Collections:||Computer Science Research Collection|
PEL Research Collection
Show full item record
This item is available under the Attribution-NonCommercial-NoDerivs 3.0 Ireland. No item may be reproduced for commercial purposes. For other possible restrictions on use please refer to the publisher's URL where this is made available, or to notes contained in the item itself. Other terms may apply.