论文标题
用于虚拟机组合并问题的剪切算法
A Cut-and-solve Algorithm for Virtual Machine Consolidation Problem
论文作者
论文摘要
虚拟机组合并问题（VMCP）试图确定要激活的服务器，如何将虚拟机（VM）分配到激活的服务器上，以及如何在服务器之间迁移VM，以使激活，分配和迁移成本的总和是将服务器和其他实践约束资源约束最小化的。在本文中，我们首先为VMCP提出了一种新的混合整数线性编程（MILP）公式。我们表明，与现有配方相比，在较小的变量或约束方面，所提出的配方更加紧凑，这使其适合解决大规模问题。然后，我们开发一种切割和解决方案（C＆S）算法，即树搜索算法，以有效地将VMCP求解为最佳性。提出的C＆S算法基于VMCP的新颖放松，该松弛比VMCP的自然连续放松提供了更强的下限，从而使搜索树较小。通过广泛的计算实验，我们表明（i）所提出的配方在溶液效率方面显着优于现有的制剂； （ii）与标准MILP求解器相比，提出的C＆S算法效率要高得多。
The virtual machine consolidation problem (VMCP) attempts to determine which servers to be activated, how to allocate virtual machines (VMs) to the activated servers, and how to migrate VMs among servers such that the summation of activated, allocation, and migration costs is minimized subject to the resource constraints of the servers and other practical constraints. In this paper, we first propose a new mixed integer linear programming (MILP) formulation for the VMCP. We show that compared with existing formulations, the proposed formulation is much more compact in terms of smaller numbers of variables or constraints, which makes it suitable for solving large-scale problems. We then develop a cut-and-solve (C&S) algorithm, a tree search algorithm to efficiently solve the VMCP to optimality. The proposed C&S algorithm is based on a novel relaxation of the VMCP that provides a stronger lower bound than the natural continuous relaxation of the VMCP, making a smaller search tree. By extensive computational experiments, we show that (i) the proposed formulation significantly outperforms existing formulations in terms of solution efficiency; and (ii) compared with standard MILP solvers, the proposed C&S algorithm is much more efficient.
