# A Multi-Objective Approach for Optimizing Virtual Machine Placement Using ILP and Tabu Search
## 3 Proposed Methods
### Mathematical Formulation of the Multi-Objective Integer Linear Programming Model
#### 3.1.2 Mathematical Formulation  
The mathematical formulation of the MOILP model is structured in three sequential stages. Each stage focuses on one key objective, ensuring that prior objectives are preserved:  
* Objective 1 (O1): Maximize the number of accepted VMs. * Objective 2 (O2): Minimize resource wastage in the DC. * Objective 3 (O3): Minimize power consumption in the DC. The stages are optimized in a lexicographical order, prioritizing O1 over O2, and O2 over O3. This ensures that the results of one stage are not compromised by subsequent stages. Figure 3 visually represents this three-stage optimization approach. This stage focuses on maximizing the total number of hosted VM requests, denoted as \(\phi_{max}\), by determining the optimal placement of VMs across PMs. Objective:  
\[Maximize\quad\phi_{max}=\sum_{i=1}^{N}\sum_{j=1}^{M}\phi_{ij} \tag{2}\]  
Subject to the following constraints:  
* Single host constraint: Each VM request \(v_{i}\) is assigned to, at most, one PM: \[\sum_{j=1}^{M}\phi_{ij}\leq 1,\quad\forall 1\leq i\leq N\] (3)
* CPU capacity constraint: The total CPU usage of the VMs assigned to PM \(P_{j}\) must not exceed the PM's available CPU capacity \(C_{j}\): \[\sum_{i=1}^{N}c_{i}\phi_{ij}\leq C_{j},\quad\forall 1\leq j\leq M\] (4)
* RAM capacity constraint: The total RAM usage of the VMs assigned to PM \(P_{j}\) must not exceed the PM's available RAM capacity \(R_{j}\): \begin{table}
\begin{tabular}{c l} \hline \hline
**Symbol** & **Description** \\ \hline \(\phi_{ij}\) & Binary decision variable, where \(\phi_{ij}=1\) if VM \(v_{i}\) is hosted by PM \(P_{j}\), and \(\phi_{ij}=0\) otherwise. \\ \hline \(\kappa_{j}\) & Binary decision variable, where \(\kappa_{j}=1\) if at least one VM is hosted by PM \(P_{j}\), \(\kappa_{j}=0\) otherwise. \\ \hline \hline \end{tabular}
\end{table} 
Table 3: _Cont._  
Figure 3: Graphical representation of the three-stage MOILP solution. \[\sum_{i=1}^{N}r_{i}\phi_{ij}\leq R_{j},\quad\forall 1\leq j\leq M \tag{5}\]
* Storage capacity constraint: The storage usage of the VMs assigned to PM \(P_{j}\) must not exceed the PM's available storage capacity \(S_{j}\): \[\sum_{i=1}^{N}s_{i}\phi_{ij}\leq S_{j},\quad\forall 1\leq j\leq M\] (6) Stage 2: Minimizing Resource Wastage--O2 Once \(\phi_{max}\), the maximum number of hosted VMs, is determined, the next objective is to minimize resource wastage, denoted as \(W_{min}\). This stage ensures that resources are used efficiently across all PMs while maintaining the number of hosted VMs unchanged from Stage 1. Objective: \[ \begin{split} Minimize\quad W_{min}=\sum_{j=1}^{M}\left(3-\left( \sum_{i=1}^{N}\left(\frac{c_{i}\phi_{ij}}{C_{j}}+\frac{r_{i}\phi_{ij}}{R_{j}}+ \frac{s_{i}\phi_{ij}}{S_{j}}\right)\right)\right)-3\left(M-\sum_{j=1}^{M} \kappa_{j}\right)\end{split} \] (7) Subject to the following constraints:
* VM hosting preservation constraint: The total number of hosted VMs must be at least equal to \(\phi_{max}\), computed in Stage 1: \[\phi_{max}\leq\sum_{i=1}^{N}\sum_{j=1}^{M}\phi_{ij}\] (8)
* VM assignment linking constraint: A VM can only be assigned to a PM if that PM is active (\(\kappa_{j}=1\)): \[\phi_{ij}\leq\kappa_{j},\quad\forall 1\leq i\leq N,\forall 1\leq j\leq M\] (9)
* PM usage indicator constraint: A PM is considered active (\(\kappa_{j}=1\)) only if it hosts at least one VM: \[\kappa_{j}\leq\sum_{i=1}^{N}\phi_{ij},\quad\forall 1\leq j\leq M\] (10) and (3)-(6). Stage 3: Minimizing Power Consumption--O3 The final stage minimizes the total power consumption, denoted as \(\mathcal{E}_{min}\). This includes the static power consumption of active PMs and the dynamic power usage associated with hosted VMs. Objective: \[ \begin{split} Minimize\quad\mathcal{E}_{min}=\sum_{j=1}^{M}\left( \left(\mathcal{E}_{j}^{1}-\mathcal{E}_{j}^{0}\right)\sum_{i=1}^{N}\left( \frac{c_{i}\phi_{ij}}{C_{j}}\right)+\mathcal{E}_{j}^{0}\kappa_{j}\right)\end{split}