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

Files in This Item:
File Description SizeFormat 
CPLEX_for_MOMRP_IJTAI_v1_BlackWhite_v2.pdf1.5 MBAdobe PDFDownload
Title: Exact and Hybrid Solutions for the Multi-objective VM Reassignment Problem
Authors: Saber, TakfarinasMarques-Silva, JoaoThorburn, JamesVentresque, 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 optimisationVM/Machine reassignmentMixed integer linear programmingLarge neighbourhood searchHybrid-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

Citations 50

Last Week
Last month
checked on Sep 11, 2020

Page view(s)

Last Week
Last month
checked on Oct 19, 2020

Download(s) 50

checked on Oct 19, 2020

Google ScholarTM



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.