×

Optimal mapping of cloud virtual machines. (English) Zbl 1351.90116

Pióro, Michał (ed.) et al., Proceedings of the 7th international network optimization conference (INOC), Warsaw, Poland, May 18–20, 2015. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 52, 93-100, electronic only (2016).
Summary: One of the challenges of cloud computing is to assign virtual machines to physical machines optimally and efficiently. The aim of telecommunication operators is to minimize the mapping cost while respecting constraints regarding location, assignment and capacity. We formulate this problem which appears to be a quadratic constrained non-convex 0-1 program. Then, we propose to lift the problem to a higher dimensional space by classical linearization, thereby handling the problem in the framework of MIP. To improve its computational performance, we employ the Reformulation-Linearization-Technique (RLT) and add valid inequalities to strengthen the model. Some preliminary numerical experiments are conducted to show the effectiveness of these methods.
For the entire collection see [Zbl 1342.90004].

MSC:

90B80 Discrete location and assignment
90C20 Quadratic programming
90C26 Nonconvex programming, global optimization
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Adams, W. P.; Sherali, H. D., A hierarchy of relaxations leading to the convex hull representation for general discrete optimization problems, Annals OR, 140, 21-47 (2005) · Zbl 1091.90060
[2] Burer, S.; Letchford, A. N., Non-convex mixed-integer nonlinear programming: A survey, Surveys in Operations Research and Management Science, 17, 97-106 (2012)
[3] Burer, S.; Saxena, A., The milp road to miqcp, (Mixed Integer Nonlinear Programming (2012), Springer), 373-405 · Zbl 1242.90122
[4] Buyya, R.; Yeo, C. S.; Venugopal, S., Market-oriented cloud computing: Vision, hype, and reality for delivering it services as computing utilities, (10th IEEE International Conference on High Performance Computing and Communications, 2008, HPCC ’08 (2008)), 5-13
[5] Karve, A.; Kimbrel, T.; Pacifici, G.; Spreitzer, M.; Steinder, M.; Sviridenko, M.; Tantawi, A., Dynamic placement for clustered web applications, (Proceedings of the 15th International Conference on World Wide Web, WWW ’06 (2006)), 595-604
[6] McCormick, G., Computability of global solutions to factorable nonconvex programs: Part i-convex underestimating problems, Mathematical Programming, 10, 147-175 (1976) · Zbl 0349.90100
[7] Sherali, H.; Adams, W., A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems, Nonconvex Optimization and Its Applications (1998), Springer
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.