gor (version 2.0)

compute_lower_bound_HK: 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)

Value

An estimate of the Held-Karp lower bound -- A scalar.

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.

Author

Cesar Asensio

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.

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