| compute_lower_bound_HK {gor} | R Documentation |
Held-Karp lower bound estimate
Description
Held-Karp lower bound estimate for the minimum distance of an optimum tour in the TSP
Usage
compute_lower_bound_HK(d, n, U, tsmall = 0.001, it = 0.2 * n, block = 100)
Arguments
d |
Distance matrix of the TSP instance. |
n |
Number of vertices of the TSP complete graph. |
U |
Upper bound of the minimum distance. |
tsmall |
Stop criterion: Is the step size decreases beyond this point the algorithm stops. Defaults to 0.001. |
it |
Iterates inside each block. Some experimentation is required to adjust this parameter: If it is large, the run time will be larger; if it is small, the accuracy will decrease. |
block |
Number of blocks of "it" iterations. In each block the size of the multiplier is halved. |
Details
An implementation of the Held-Karp iterative algorithm towards the minimum distance tour of a TSP instance. As the algorithm converges slowly, only an estimate will be achieved. The accuracy of the estimate depends on the stopping requirements through the number of iteration blocks "block" and the number of iterations per block "it", as well as the smallest allowed multiplier size "tsmall": When it is reached the algorithm stops. It is also crucial to a good estimate the quality of the upper bound "U" obtained by other methods.
The Held-Karp bound has the following uses: (1) assessing the quality of solutions not known to be optimal; (2) giving an optimality proof of a given solution; and (3) providing the "bound" part in a branch-and-bound technique.
Please note that recommended computation of the Held-Karp bound uses Lagrangean relaxation on an integer programming formulation of the TSP, whereas this routine uses the Cook algorithm to be found in the reference below.
Value
An estimate of the Held-Karp lower bound – A scalar.
Author(s)
Cesar Asensio
References
Cook et al. Combinatorial Optimization (1998) sec. 7.3.
See Also
compute_distance_matrix computes distance matrix of a set of points, build_tour_nn_best builds a tour using the best-nearest-neighbor heuristic, improve_tour_2opt improves a tour using 2-opt, improve_tour_3opt improves a tour using 3-opt, compute_lower_bound_1tree computes the 1-tree lower bound.
Examples
m <- 10 # Generate some points in the plane
z <- cbind(c(rep(0,m), rep(2,m), rep(5,m), rep(7,m)), rep(seq(0,m-1),4))
n <- nrow(z)
d <- compute_distance_matrix(z)
b <- build_tour_nn_best(d, n)
b$distance # Distance 48.6055
bi <- improve_tour_2opt(d, n, b$tour)
bi$distance # Distance 48 (optimum)
compute_lower_bound_HK(d,n,U=48.61) # 45.927
compute_lower_bound_HK(d,n,U=48.61,it=20,tsmall=1e-6) # 45.791
## Random points
set.seed(1)
n <- 25
z <- cbind(runif(n,min=1,max=10),runif(n,min=1,max=10))
d <- compute_distance_matrix(z)
bn <- build_tour_nn_best(d,n)
b3 <- improve_tour_3opt(d,n,bn$tour)
b3$distance # 35.08155
compute_lower_bound_HK(d, n, U=35.1) # 34.80512
compute_lower_bound_HK(d, n, U=35.0816, it=20) # 35.02892
compute_lower_bound_HK(d, n, U=35.0816, tsmall = 1e-5) # 34.81119
compute_lower_bound_HK(d, n, U=35.0816, it=50, tsmall = 1e-9) # 35.06789