## 4 Solution Procedure
### Sub-Gradiant Method
In addition, in LD the upper bound obtained from the first approach--i.e., the heuristic lower bound (LD-HLB)--could generate better bounds. More test problems with larger size have been solved using the proposed methods. A mentioned earlier CPLEX was able to solve problems up to 300 points. Therefore, for the test problems in this section, there are no optimal solutions to be used for the evaluation of the bounds. To be able to measure the tightness of the bounds produced for large problems we use the bounds duality gap as

\[duality\;gap=\frac{(Upper\;bound-Lower\;bound)}{Lower\;bound}\]

The column under 'Gap' includes the calculated duality gaps for the studied test instances. The first approach i.e., calculating the lower bound using feasible solutions by \(Z_{LB}\) has been utilized to solve large test instances. Table 10 includes the computational results for LR1, LR2, and LD. According to Table 10, LD and LR2 were not able to find feasible solutions as the lower bound for most of the problems. The reason for this fact can be because of the decomposition structure that LD uses to obtain the variables. Although LD did not have good performance to produce lower bounds for some problems, it should be highlighted that the upper bounds computed with LD are less than LR1 and LR2 for almost all problems (except for instance numbers 14 and 16). Similarly comparing the lower bounds, it is apparent that LR2 can produce higher values for lower bounds and the tightness of the bounds calculated using the gap is also better in LR2. Regarding the computational time, LR1 has relatively less computational time, especially for larger instances but LR1 is not generating good bounds. Between LR2 and LD that obtain the best bounds, the average computational time is the best in LD-LB. Table 11 shows the results for LR1, LR2, and LD when the fixed lower bound obtained from the heuristic method is used in the solving procedure. The computational effort for LD is considerably lower compared to LR1 and LR2. Between LR1 and LR2, the computational time is relatively less for LR2. Similarly, the performance of LD to produce better upper bounds is obvious from the average duality gap that is 0.3 for LD, while these values are 0.37 and 0.41 for LR1 and LR2. To summarize the results obtained from the conducted tests, Table 12 is generated. For all test problems, the best obtained lower bound and the best obtained upper bound together with the methods that they are computed, are extracted. According to Table 12, HLB and LR2-LB could produce best lower bounds (except for the test problem #3). From 19 test problems, HLB could obtain the best lower bounds for 14 problems while LR2-LB obtained the best lower bound for four problems (in case #2, they obtain the same result). This fact improves the efficiency of the proposed heuristic method to compute feasible solutions as the lower bound of the problems. Regarding the upper bound, the competition is mainly between LD-HLB and LD-LB (except for two test problems 1 and 4). In particular, this fact improves that the best upper bounds are obtained from the LD problem. From 18 test problems, LD-HLB could produce best upper bounds for 10 problems, the upper