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

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.