# A Multi-Objective Approach for Optimizing Virtual Machine Placement Using ILP and Tabu Search
## 3 Proposed Methods  
This section presents the proposed methods for solving the VMPP, focusing on their contributions to addressing the limitations of existing approaches.  
We introduce a novel solution by combining two advanced methods: a Multi-Objective Integer Linear Programming (MOILP) model and a Multi-Objective Tabu Search (MOTS) meta-heuristic. To the best of our knowledge, MOTS is applied for the first time to address the VMPP.  
The key innovation of this study lies in addressing the limitations of MOILP in large-scale cloud environments. While MOILP provides a precise mathematical framework for optimizing conflicting objectives, its computational cost and inefficiency grow exponentially with the size of the problem, especially with thousands of VMs and PMs. As the complexity of MOILP increases, it struggles with long solution times and high resource demands, making it unsuitable for real-time or dynamic cloud scenarios.  
To address these challenges, we employ MOTS, a TS-based optimization technique that is highly effective in solving complex problems. MOTS improves local search processes by utilizing a memory-based approach, which helps it avoid getting trapped in local optima. The method explores the solution space methodically, permitting moves that may initially worsen the objective, and uses a tabu list--a short-term memory mechanism--to prevent revisiting recently explored solutions. This approach ensures greater diversity and directs the search toward high-quality solutions [40; 41]. MOTS improves computational efficiency, accelerates convergence, and enhances scalability, making it particularly suited for dynamic environments with larger solution spaces.  
The combination of MOILP and MOTS provides a unique balance of theoretical rigor and practical scalability, making it an ideal solution for large-scale cloud environments. The study simultaneously optimizes three critical objectives to improve VMP:  
* Maximizing hosted VMs: This objective aims to optimize PM utilization, increasing cloud profitability by hosting more clients.
* Minimizing resource wastage: Efficient allocation of CPU, memory, and storage prevents over-provisioning and enhances server performance. Unbalanced residual resources can limit future VM placements. Resource wastage is calculated as the sum of normalized residuals for each dimension, with greater discrepancies leading to more waste [42]. For instance, a server with unused RAM but insufficient CPU cannot accommodate more VMs. Figure 2 shows the VMP for three VMs over a PM. The total CPU and RAM capacities are represented among the x-axis and y-axis respectively. Placing three VMs on the host reduces its resource capacity across the two dimensions,with each small rectangle representing the resources allocated to a VM. The dark gray area indicates the remaining residual resources available for future allocation. In the example of Figure 2a, the host has substantial unused RAM capacity but limited CPU, which prevents it from accommodating any additional VMs due to CPU shortage. Figure 2b shows a VMP scenario where CPU and memory utilization reaches 90%, indicating that all dimensions are balanced, and the PM is being fully utilized.
* Minimizing energy consumption: Reducing power usage lowers operational costs and environmental impact. Energy consumption primarily depends on CPU usage, calculated using the formula [35] \[\mathcal{E}_{j}=(\mathcal{E}_{j}^{1}-\mathcal{E}_{j}^{0})\times U_{j}+ \mathcal{E}_{j}^{0}\] (1) where \(U_{j}\) is the normalized CPU usage on PM \(P_{j}\) (\(U_{j}\in[0,1]\)), and \(\mathcal{E}_{j}^{1}\) and \(\mathcal{E}_{j}^{0}\) are the power values when the PM is busy or idle, respectively. We assume that CPU consumes the most energy compared to other resources like memory and storage, though the model can be extended to include other parameters.  
Balancing these objectives enables effective trade-offs between performance, cost, and energy efficiency in cloud environments.