A Lagrange decomposition based Branch and Bound algorithm for the Optimal Mapping of Cloud Virtual Machines
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.
Entry Submitted: 06/22/2018
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|