A Lagrange decomposition based Branch and Bound algorithm for the Optimal Mapping of Cloud Virtual Machines

Autor: Walid Ben-Ameur, Guanglei Wang, Adam Ouorou
Přispěvatelé: Research School of Computer Science [Canberra], Australian National University (ANU), Département Réseaux et Services Multimédia Mobiles (RS2M), Institut Mines-Télécom [Paris] (IMT)-Télécom SudParis (TSP), Institut Polytechnique de Paris (IP Paris), Méthodes et modèles pour les réseaux (METHODES-SAMOVAR), Services répartis, Architectures, MOdélisation, Validation, Administration des Réseaux (SAMOVAR), Institut Mines-Télécom [Paris] (IMT)-Télécom SudParis (TSP)-Institut Mines-Télécom [Paris] (IMT)-Télécom SudParis (TSP), Centre National de la Recherche Scientifique (CNRS), Orange Labs [Chatillon], Orange Labs
Jazyk: angličtina
Rok vydání: 2018
Předmět:
Lagrange decomposition
Mathematical optimization
Information Systems and Management
General Computer Science
Computer science
0211 other engineering and technologies
Structure (category theory)
Cloud computing
02 engineering and technology
Management Science and Operations Research
[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
computer.software_genre
Industrial and Manufacturing Engineering
Integerprogramming
0502 economics and business
[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
Decomposition (computer science)
FOS: Mathematics
Mathematics - Optimization and Control
050210 logistics & transportation
021103 operations research
Branch and bound
business.industry
05 social sciences
[INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO]
Virtual machine assignment
Virtual machine
Optimization and Control (math.OC)
Modeling and Simulation
Relaxation (approximation)
[MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC]
Variety (universal algebra)
business
computer
Zdroj: European Journal of Operational Research
European Journal of Operational Research, Elsevier, 2019, 276 (1), pp.28-39. ⟨10.1016/j.ejor.2018.12.037⟩
ISSN: 0377-2217
Popis: One of the challenges of cloud computing is to optimally and efficiently assign virtual ma- chines to physical machines. The aim of telecommunication operators is to minimize the map- ping cost while respecting constraints regarding location, assignment and capacity. In this paper we first propose an exact formulation leading to a 0-1 bilinear constrained problem. Then we introduce a variety of linear cuts by exploiting the problem structure and present a Lagrange decomposition based B&B algorithm to obtain optimal solutions efficiently. Numerically, we show that our valid inequalities close over 80% of the optimality gap incurred by the well-known McCormick relaxation, and demonstrate the computational advantage of the proposed B&B algorithm with extensive numerical experiments.
submitted for journal publication; copyright preserved
Databáze: OpenAIRE
Externí odkaz: