A cut-and-solve algorithm for virtual machine consolidation problem

The virtual machine consolidation problem attempts to determine which servers to be activated, how to allocate virtual machines to the activated servers, and how to migrate virtual machines 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 formulation for the virtual machine consolidation problem. 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 algorithm, a tree search algorithm to efficiently solve the virtual machine consolidation problem to optimality. The proposed cut-and-solve algorithm is based on a novel relaxation of the virtual machine consolidation problem that provides a stronger lower bound than the natural continuous relaxation of the virtual machine consolidation problem, 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; (ii) compared with standard mixed integer linear programming solvers, the proposed cut-and-solve algorithm is much more efficient; and (iii) compared with an existing heuristic algorithm, the proposed cut-and-solve algorithm is better able to balance workload distribution across servers and achieve higher resource utilization.