# insert_dummy

##### Insert dummy cities into a distance matrix

Inserts dummy cities into objects of class `TSP`

or `ATSP`

. A
dummy city has the same, constant distance (0) to all other cities and is
infinitely far from other dummy cities. A dummy city can be used to transform
a shortest Hamiltonian path problem (i.e., finding an optimal linear order)
into a shortest Hamiltonian cycle problem which can be solved by a TSP
solvers (Garfinkel 1985).
Several dummy cities can be used together with a TSP solvers to perform
rearrangement clustering (Climer and Zhang 2006).

- Keywords
- manip

##### Usage

`insert_dummy(x, n = 1, const = 0, inf = Inf, label = "dummy")`

##### Arguments

- x
- an object of class
`TSP`

or`ATSP`

. - n
- number of dummy cities.
- const
- distance of the dummy cities to all other cities.
- inf
- distance between dummy cities.
- label
- labels for the dummy cities. If only one label is given, it is reused for all dummy cities.

##### Details

The dummy cities are inserted after the other cities in `x`

.

A `const`

of 0 is guaranteed to work if the TSP finds the optimal
solution. For heuristics returning suboptimal solutions, a higher
`const`

(e.g., `2 * max{x}`

) might provide better results.

##### References

Sharlee Climer, Weixiong Zhang (2006): Rearrangement Clustering: Pitfalls,
Remedies, and Applications, *Journal of Machine Learning Research*
**7**(Jun), pp. 919--943.

R.S. Garfinkel (1985): Motivation and modelling (chapter 2). In: E. L. Lawler, J. K. Lenstra, A.H.G. Rinnooy Kan, D. B. Shmoys (eds.) The traveling salesman problem - A guided tour of combinatorial optimization, Wiley \& Sons.

##### See Also

##### Examples

```
## make runs comparable
set.seed(4444)
data("iris")
tsp <- TSP(dist(iris[-5]))
## insert 2 dummy cities
tsp_dummy <- insert_dummy(tsp, n = 2, label = "boundary")
## get a solution for the TSP
tour <- solve_TSP(tsp_dummy)
## plot the distance matrix
image(tsp_dummy, tour)
## draw lines where the dummy cities are located
abline(h = which(labels(tour)=="boundary"), col = "red")
abline(v = which(labels(tour)=="boundary"), col = "red")
```

*Documentation reproduced from package TSP, version 1.1-4, License: GPL-3*