# A Multi-Objective Approach for Optimizing Virtual Machine Placement Using ILP and Tabu Search
###### Abstract  
Efficient Virtual Machine (VM) placement is a critical challenge in optimizing resource utilization in cloud data centers. This paper explores both exact and approximate methods to address this problem. We begin by presenting an exact solution based on a Multi-Objective Integer Linear Programming (MOILP) model, which provides an optimal VM Placement (VMP) strategy. Given the NP-completeness of the MOILP model when handling large-scale problems, we then propose an approximate solution using a Tabu Search (TS) algorithm. The TS algorithm is designed as a practical alternative for addressing these complex scenarios. A key innovation of our approach is the simultaneous optimization of three performance metrics: the number of accepted VMs, resource wastage, and power consumption. To the best of our knowledge, this is the first application of a TS algorithm in the context of VMP. Furthermore, these three performance metrics are jointly optimized to ensure operational efficiency (OPEF) and minimal operational expenditure (OPEX). We rigorously evaluate the performance of the TS algorithm through extensive simulation scenarios and compare its results with those of the MOILP model, enabling us to assess the quality of the approximate solution relative to the optimal one. Additionally, we benchmark our approach against existing methods in the literature to emphasize its advantages. Our findings demonstrate that the TS algorithm strikes an effective balance between efficiency and practicality, making it a robust solution for VMP in cloud environments. The TS algorithm outperforms the other algorithms considered in the simulations, achieving a gain of 2% to 32% in OPEF, with a worst-case increase of up to 6% in OPEX. cloud computing; virtualization; virtual machines; placement problem; multi-objective optimization; integer linear programming; tabu search; ant colony optimization; genetic algorithm; first fit; first fit decreasing; worst fit +
Footnote †: journal: _et alc
can result in wasted resources, reduced performance, and violations of Service Level Agreements (SLAs), underscoring the importance of robust solutions. The complexity of the VMPP stems from multiple interrelated factors [4]. Resource heterogeneity in modern cloud environments complicates the matching of VM requirements to available PMs. The sheer scale of DCs introduces a combinatorial challenge as the number of potential VM-PM allocations grows exponentially with infrastructure size. Additionally, balancing conflicting objectives--such as minimizing energy consumption, reducing costs, ensuring Quality of Service (QoS), and adhering to SLAs--requires strategic prioritization. Dynamic workloads and fluctuating resource demands further amplify these challenges, necessitating adaptable and real-time solutions. These factors significantly impact cloud operational efficiency (OPEF) and sustainability [5]. High energy consumption increases costs and contributes to carbon emissions, making energy-efficient strategies vital for reducing environmental impact. Effective resource utilization is critical to avoiding under-utilization, which wastes resources, and over-utilization, which causes performance bottlenecks and degrades QoS. SLA compliance is also essential to avoid penalties and maintain client satisfaction, requiring careful management of latency and workload distribution. Finally, scalability and adaptability are paramount for accommodating infrastructure growth and dynamic workloads, ensuring reliable performance under changing conditions. Traditional methods, such as greedy algorithms or single-objective optimization techniques, often fall short in addressing the multifaceted nature of the VMPP. These methods typically focus on optimizing a single objective (e.g., minimizing energy consumption or maximizing resource utilization), neglecting the interdependencies and trade-offs that exist between competing objectives in real-world cloud environments.