A Lagrange decomposition based branch and bound algorithm for the optimal mapping of cloud virtual machines

Guanglei Wang, Walid Ben-Ameur and Adam Ouorou

European Journal of Operational Research, 2019, vol. 276, issue 1, 28-39

Abstract: One of the challenges of cloud computing is to optimally and efficiently assign virtual machines to physical machines. The aim of telecommunication operators is to minimize the mapping 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 branch and bound 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.

Keywords: Integer programming; Virtual machine assignment; Lagrange decomposition; Branch and bound (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221718311111
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:276:y:2019:i:1:p:28-39

DOI: 10.1016/j.ejor.2018.12.037

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().