## 5 Description of the Heuristics
### Second Phase: Maximum Edge Disjoint Path Problem (MEDPP)--Greedy Heuristics
\begin{table}
\begin{tabular}{c c c c c c c c c c c c} \hline \hline  & \multicolumn{3}{c}{**ILP (1800 [s])**} & \multicolumn{3}{c}{\(MAX\_ITER=0\)} & \multicolumn{3}{c}{\(MAX\_ITER=20\)} & \multicolumn{3}{c}{\(MAX\_ITER=50\)} \\ \hline \(U\) & **Flows** & **N\_Saving\_F** & **Flows** & **N\_Saving\_F** & **Time** & **Flows** & **N\_Saving\_F** & **Time** & **Flows** & **N\_Saving\_F** & **Time** \\ \hline
0.2 & 30 & 87.01 & 30 & 83.84 & 0.05 & 30 & 83.84 & 0.06 & 30 & 83.84 & 0.07 \\
0.4 & 30 & 73.13 & 30 & 69.17 & 0.09 & 3



When considering the scheduling by activations, CPLEX finds a solution for the first objective for the lowest utilization factors, 0.2 and 0.4, but--as in the case of flows--no optimal solution is reached for the minimization of energy demand within the time limit of 1800 [s]. However, the heuristic can solve the problem in all cases with less than a second computation. Figure 5 shows the results and, as in the previous case, the CPLEX results are taken as a reference. The percentage of energy saving is in the right axis and the percentage of activations scheduled is on the left one. When reading the results, it may appear contradictory that with more iterations in the final phase the heuristic presents less energy savings when the utilization factor increases. However, the reader should pay attention to the fact that, for both approaches, flows or activations, when more iterations are done in the final phase, a higher percentage of flows or activations are scheduled. This clearly increases the energy demand. Figure 4: Maximizing the flow scheduling approach. Figure 5: Maximizing activation scheduling. In Figure 5, it may appear that the energy saving improves greatly with higher utilization factors. This result can be explained as what is shown is the relation to the CPLEX values and as explained before, the solver was not able to find a good solution within the time limit. This clearly leaves the CPLEX value more close to the heuristic solution found. A more complex system was simulated based on the good results obtained in this first experiment. As before, five instances for a system with 12 eight servers and 1000 flows were randomly generated following the same method for each utilization factor. The ILP model in CPLEX was impossible to run as the number of variables was too large even for a 64 GB RAM machine. The results are presented in Tables 6-9, for the cases of using the Simple or Multistart Ad-Hoc for the second stage with flow or activations scheduling, respectively. Multistart results are not presented as they are part of the Ad-Hoc implementation, which improves the solutions found. In these cases, the relation is made to the nominal system as it was not possible to run the CPLEX solver. Figure 6 presents the results for the Simple heuristic with the flow scheduling approach. This shows, on the left axis, the percentage of energy saved with respect to all the network elements active and, on the right axis, the percentage of flows scheduled. As can be seen, although the energy saved is less when more iterations are made in the third phase, there is an increase in the number of flows scheduled. However, there is no significant improvement in doing 50 iterations compared to only 20, while there is an important increase in the computation time. Figure 7 presents the results for the Simple heuristic with the activation scheduling approach. It shows, on the left axis, the percentage of energy saved with respect to all the network elements active and, on the right axis, the percentage of activations scheduled. As can be seen, although the energy saved is less when more iterations are made in the third phase, there is an increase in the number of activations scheduled. However, there is no significant improvement in doing 50 iterations compared to only 20, while there is an important increase in the computation time of about 50%. Figure 6: Simple heuristic, flow scheduling. Figure 7: Simple heuristic, activation scheduling.