NAG Library Function Document

nag_mip_tsp_simann (h03bbc)

1  Purpose

2  Specification

3  Description

4  References

5  Arguments

1:    $\mathbf{nc}$ – IntegerInput

On entry: the number of cities. In the trivial cases $\mathbf{nc}=1$, $2$ or $3$, the function returns the optimal solution immediately with $\mathbf{tmode}=0$ (provided the relevant distance matrix entries are not negative).

Constraint: $\mathbf{nc}\ge 1$.

2:    $\mathbf{dm}\left[\mathbf{nc}\times \mathbf{nc}\right]$ – const doubleInput

Note: the $\left(i,j\right)$th element of the matrix is stored in $\mathbf{dm}\left[\left(j-1\right)\times \mathbf{nc}+i-1\right]$.

On entry: the distance matrix; each $\mathbf{dm}\left[\left(\mathit{j}-1\right)\times \mathbf{nc}+\mathit{i}-1\right]$ is the effective cost or weight between nodes $\mathit{i}$ and $\mathit{j}$. Only the strictly upper half of the matrix is referenced.

Constraint: $\mathbf{dm}\left[\left(\mathit{j}-1\right)\times \mathbf{nc}+\mathit{i}-1\right]\ge 0.0$, for $\mathit{j}=2,3,\dots ,\mathbf{nc}$ and $\mathit{i}=1,2,\dots ,\mathit{j}-1$.

3:    $\mathbf{bound}$ – doubleInput

On entry: a lower bound on the solution. If the optimum is unknown set bound to zero or a negative value; the function will then calculate the minimum spanning tree for dm and use this as a lower bound (returned in $\mathbf{alg\_stats}\left[5\right]$). If an optimal value for the cost is known then this should be used for the lower bound. A detailed discussion of relaxations for lower bounds, including the minimal spanning tree, can be found in Reinelt (1994).

4:    $\mathbf{targc}$ – doubleInput

On entry: a measure of how close an approximation needs to be to the lower bound. The function terminates when a cost is found less than or equal to $\mathbf{bound}+\mathbf{targc}$. This argument is useful when an optimal value for the cost is known and supplied in bound. It may be sufficient to obtain a path that is close enough (in terms of cost) to the optimal path; this allows the algorithm to terminate at that point and avoid further computation in attempting to find a better path.

If $\mathbf{targc}<0$, $\mathbf{targc}=0$ is assumed.

5:    $\mathbf{path}\left[\mathbf{nc}\right]$ – IntegerOutput

On exit: the best path discovered by the simulation. That is, path contains the city indices in path order. If $\mathbf{fail}\mathbf{.}\mathbf{code}\ne 0$ on exit, path contains the indices $1$ to nc.

6:    $\mathbf{cost}$ – double *Output

On exit: the cost or weight of path. If $\mathbf{fail}\mathbf{.}\mathbf{code}\ne 0$ on exit, cost contains the largest model real number (see nag_real_max_exponent (X02BLC)).

7:    $\mathbf{tmode}$ – Integer *Output

On exit: the termination mode of the function (if $\mathbf{fail}\mathbf{.}\mathbf{code}\ne 0$ on exit, tmode is set to $-1$):

$\mathbf{tmode}=0$

Optimal solution found, $\mathbf{cost}=\mathbf{bound}$.

$\mathbf{tmode}=1$

System temperature cooled. The algorithm returns a path and associated cost that does not attain, nor lie within targc of, the bound. This could be a sufficiently good approximation to the optimal path, particularly when $\mathbf{bound}+\mathbf{targc}$ lies below the optimal cost.

$\mathbf{tmode}=2$

Halted by cost falling within the desired targc range of the bound.

$\mathbf{tmode}=3$

System stalled following lack of improvement.

$\mathbf{tmode}=4$

Initial search failed to find a single improvement (the solution could be optimal).

8:    $\mathbf{alg\_stats}\left[6\right]$ – doubleOutput

On exit: an array of metrics collected during the initial search. These could be used as a basis for future optimization. If $\mathbf{fail}\mathbf{.}\mathbf{code}\ne 0$ on exit, the elements of alg_stats are set to zero; the first five elements are also set to zero in the trival cases $\mathbf{nc}=1$, $2$ or $3$.

$\mathbf{alg\_stats}\left[0\right]$

Mean delta.

$\mathbf{alg\_stats}\left[1\right]$

Standard deviation of deltas.

$\mathbf{alg\_stats}\left[2\right]$

Cost at end of initial search phase.

$\mathbf{alg\_stats}\left[3\right]$

Best cost encountered during search phase.

$\mathbf{alg\_stats}\left[4\right]$

Initial system temperature. At the end of stage 1 of the algorithm, this is a function of the mean and variance of the deltas, and of the distance from best cost to the lower bound. It is a measure of the initial acceptance criteria for stage 2. The larger this value, the more iterations it will take to geometrically reduce it during stage 2 until the system is cooled (below a threshold value).

$\mathbf{alg\_stats}\left[5\right]$

The lower bound used, which will be that computed internally when $\mathbf{bound}\le 0$ on input. Subsequent calls with different random states can set bound to the value returned in $\mathbf{alg\_stats}\left[5\right]$ to avoid recomputation of the minimal spanning tree.

9:    $\mathbf{state}\left[\mathit{dim}\right]$ – IntegerCommunication Array

Note: the dimension, $\mathit{dim}$, of this array is dictated by the requirements of associated functions that must have been previously called. This array MUST be the same array passed as argument state in the previous call to nag_rand_init_repeatable (g05kfc) or nag_rand_init_nonrepeatable (g05kgc).

On entry: a valid RNG state initialized by nag_rand_init_repeatable (g05kfc) or nag_rand_init_nonrepeatable (g05kgc). Since the algorithm used is stochastic, a random number generator is employed; if the generator is initialized to a non-repeatable sequence (nag_rand_init_nonrepeatable (g05kgc)) then different solution paths will be taken on successive runs, returning possibly different final approximate solutions.

On exit: contains updated information on the state of the generator.

10:  $\mathbf{fail}$ – NagError *Input/Output

The NAG error argument (see Section 2.7 in How to Use the NAG Library and its Documentation).

6  Error Indicators and Warnings

NE_ALLOC_FAIL

Dynamic memory allocation failed.
See Section 2.3.1.2 in How to Use the NAG Library and its Documentation for further information.

NE_BAD_PARAM

On entry, argument $〈\mathit{\text{value}}〉$ had an illegal value.

NE_INT

On entry, $\mathbf{nc}=〈\mathit{\text{value}}〉$.
Constraint: $\mathbf{nc}\ge 1$.

NE_INTERNAL_ERROR

An internal error has occurred in this function. Check the function call and any array sizes. If the call is correct then please contact NAG for assistance.

An unexpected error has been triggered by this function. Please contact NAG.
See Section 2.7.6 in How to Use the NAG Library and its Documentation for further information.

NE_INVALID_STATE

On entry, state vector has been corrupted or not initialized.

NE_NO_LICENCE

Your licence key may have expired or may not have been installed correctly.
See Section 2.7.5 in How to Use the NAG Library and its Documentation for further information.

NE_REAL_ARRAY

On entry, the strictly upper triangle of dm had a negative element.

7  Accuracy

8  Parallelism and Performance

9  Further Comments

10  Example

10.1  Program Text

Program Text (h03bbce.c)

10.2  Program Data

Program Data (h03bbce.d)

10.3  Program Results

Program Results (h03bbce.r)