Paper Info
Title
Exact And Hybrid Solutions For The Multi-Objective Vm Reassignment Problem
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).
Year
DOI
Venue
2017
10.1142/S0218213017600041
INTERNATIONAL JOURNAL ON ARTIFICIAL INTELLIGENCE TOOLS
Keywords
Field
DocType
Multi-objective optimisation, VM/machine reassignment, mixed integer linear programming, large neighbourhood search, hybrid-metaheuristics
Integer,Heuristic,Mathematical optimization,Computer science,Constraint programming,Integer programming,Artificial intelligence,Solver,Machine learning,Metaheuristic
Journal
Volume
Issue
ISSN
26
1
0218-2130
Citations 
PageRank 
References 
4
0.39
30
Authors
4
Name
Order
Citations
PageRank
Takfarinas Saber1254.90
Joao Marques-Silva21947124.04
James Thorburn3264.11
Anthony Ventresque410817.08