Optimization Online


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

Guanglei Wang(guanglei.wang13***at***gmail.com)
Walid Ben-Ameur(walid.benameur***at***telecom-sudparis.eu )
Adam Ouorou( adam.ouorou***at***orange.com)

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 mini- mize 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 prob- lem 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: Virtualmachineassignment,0-1 bilinearoptimization,Lagrange decomposition, Branch and bound

Category 1: Applications -- OR and Management Sciences

Category 2: Combinatorial Optimization (Branch and Cut Algorithms )

Category 3: Integer Programming (0-1 Programming )

Citation: Working paper, Orange Labs Research, 06/2018.

Download: [PDF]

Entry Submitted: 06/22/2018
Entry Accepted: 06/22/2018
Entry Last Modified: 06/22/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society