## 4 Solution Procedure
### Sub-Gradiant Method
\begin{table}
\begin{tabular}{c c c c|c c c|c c c c c} \hline \hline  & \multicolumn{2}{c}{**CPLEX**} & \multicolumn{2}{c}{**Heuristic**} & \multicolumn{2}{c}{**LR2-HLB**} & \multicolumn{4}{c}{**LR2-LB**} \\ \cline{2-13} \# & **Obj** & **Time** & **HLB** & **UB** & **Time** & **UO-Gap** & **LB** & **UB** & **Time** & **LO-Gap** & **UO-Gap** \\ \hline
1 & 56 & 1 & 55 & 72 & 30 & 0.286 & 36 & 72 & 40 & 0.56 & 0.286 \\
2 & 71 & 2 & 69 & 98 & 33 & 0.380 & 69 & 98 & 49 & 0.03 & 0.380 \\
3 & 85 & 2 & 80 & 109 & 40 & 0.282 & 47 & 109 & 52 & 0.81 & 0.282 \\
4 & 114 & 2 & 114 & 151 & 59 & 0.325 & 68 & 117 & 93 & 0.676 & 0.026 \\
5 & 1838 & 333 & 1617 & 2232 & 190 & 0.214 & 1764 & 2232 & 372 & 0.04 & 0.214 \\
6 & 2030 & 338 & 1819 & 2388 & 267 & 0.176 & 1907 & 2388 & 513 & 0.06 & 0.176 \\
7 & 2847 & 1002 & 2574 & 3394 & 280 & 0.192 & 2634 & 3393 & 578 & 0.08 & 0.192 \\
8 & 3056 & 503 & 2906 & 3600 & 372 & 0.178 & 2894 & 3600 & 574 & 0.06 & 0.178 \\ Average & & & & 158 & 0.254 & & & 283 & 0.289 & 0.217 \\ \hline \hline \end{tabular}
\end{table} 
Table 8: Computational results to compare CPLEX and LR2 for small size instances. \begin{table}
\begin{tabular}{c c c c|c c c|c c c c} \hline \hline  & \multicolumn{2}{c}{**CPLEX**} & \multicolumn{2}{c}{**Heuristic**} & \multicolumn{2}{c}{**LR2-HLB**} & \multicolumn{4}{c}{**LR2-LB**} \\ \cline{2-13} \# & **Obj** & **Time** & **HLB** & **UB** & **Time** & **UO-Gap** & **LB** & **UB** & **Time** & **LO-Gap** & **UO-Gap** \\ \hline
1 & 56 & 1 & 55 & 52 & 1 & \(-\)0.071 & 24 & 51 & 77 & 1.333 & \(-\)0.089 \\
2 & 71 & 2 & 69 & 80 & 51 & 0.127 & - & 80 & 51 & & 0.127 \\
3 & 85 & 2 & 80 & 99 & 51 & 0.165 & 46 & 102 & 61 & 0.848 & 0.200 \\
4 & 114 & 2 & 114 & 128 & 52 & 0.123 & 33 & 134 & 60 & 2.455 & 0.175 \\
5 & 1838 & 333 & 1617 & 2120 & 148 & 0.153 & 1586 & 2122 & 333 & 0.159 & 0.155 \\
6 & 2030 & 338 & 1819 & 2280 & 177 & 0.123 & 1755 & 2280 & 242 & 0.157 & 0.123 \\
7 & 2847 & 1002 & 2574 & 3193 & 296 & 0.122 & 2317 & 3190 & 257 & 0.229 & 0.120 \\
8 & 3056 & 503 & 2906 & 3456 & 275 & 0.131 & 2632 & 3456 & 453 & 0.161 & 0.131 \\ Average & & & & 131 & 0.135 & & & 191 & 0.763 & 0.147 \\ \hline \hline \end{tabular}
\end{table} 
Table 9: Computational results to compare CPLEX and LD for small size instances. by substituting the heuristic lower bound and compute the upper bounds. The results for this approach are reported under column \"LR1-HLB\" in Table 7. Tables 8 and 9 illustrate the same results for LR2 and LD respectively. In Table 7, the upper bounds obtained with LR1-LB are almost the same as LR1-HLB but computational time is less in LR1-HLB for all cases. Similarly, comparing the upper bounds and the computational times for LR2, this fact holds as well. LR2-LB and LR2-HLB obtain the same upper bounds (except in instance 4) while the computational performance of LR2-HLB is better than LR2-LB. The average value for \"UO-gap\" does not show a very significant difference for LR1-LB and LR1-HLB. For LD, LD-HLB has a little bit better performance regarding the upper bounds quality and the computational effort is better for all cases. Regarding the computational time, the procedure using the lower bound of the heuristic method is superior in all problems. According to the results of Tables 7-9, it seems that for LR1, LR2 and LD both methods can obtain the same upper bounds but the computational time of HLB procedure is less. The last row of each table contains the average values of the upper bound and lower bound optimality gaps. These average values can be used to evaluate the performance of the conducted approaches on the obtained bounds. Among all the methods, the heuristic method produces a tighter lower bound with the average amount of 0.065 (Table 6), but among LR1, LR2, and LD the performance of the LR1 has superiority to the others with the average lower bound optimality gap (LO-gap) equal to 0.169. On the contrary, LD has the best performance regarding the upper bound optimality gap. The upper bound optimality gaps of both approaches for LD are better than LR1 and LR2.