% Generated by roxygen2: do not edit by hand
% Please edit documentation in R/insert_dummy.R
\name{insert_dummy}
\alias{insert_dummy}
\alias{insert_dummy.TSP}
\alias{insert_dummy.ATSP}
\alias{insert_dummy.ETSP}
\title{Insert dummy cities into a distance matrix}
\usage{
insert_dummy(x, n = 1, const = 0, inf = Inf, label = "dummy")

\method{insert_dummy}{TSP}(x, n = 1, const = 0, inf = Inf, label = "dummy")

\method{insert_dummy}{ATSP}(x, n = 1, const = 0, inf = Inf, label = "dummy")

\method{insert_dummy}{ETSP}(x, n = 1, const = 0, inf = Inf, label = "dummy")
}
\arguments{
\item{x}{an object with a TSP problem.}

\item{n}{number of dummy cities.}

\item{const}{distance of the dummy cities to all other cities.}

\item{inf}{distance between dummy cities.}

\item{label}{labels for the dummy cities. If only one label is given, it is
reused for all dummy cities.}
}
\value{
returns an object of the same class as \code{x}.
}
\description{
Inserts dummy cities into a TSP problem.  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).
}
\details{
Several dummy cities can be used together with a TSP solvers to perform
rearrangement clustering (Climer and Zhang 2006).

The dummy cities are inserted after the other cities in \code{x}.

A \code{const} of 0 is guaranteed to work if the TSP finds the optimal
solution. For heuristics returning suboptimal solutions, a higher
\code{const} (e.g., \code{2 * max(x)}) might provide better results.
}
\examples{
## Example 1: Find a short Hamiltonian path
set.seed(1000)
x <- data.frame(x = runif(20), y = runif(20), row.names = LETTERS[1:20])

tsp <- TSP(dist(x))

## add a dummy city to cut the tour into a path
tsp <- insert_dummy(tsp, label = "cut")
tour <- solve_TSP(tsp)
tour

plot(x)
lines(x[cut_tour(tour, cut = "cut"),])


## Example 2: Rearrangement clustering of the iris dataset
set.seed(1000)
data("iris")
tsp <- TSP(dist(iris[-5]))

## insert 2 dummy cities to creates 2 clusters
tsp_dummy <- insert_dummy(tsp, n = 3, label = "boundary")

## get a solution for the TSP
tour <- solve_TSP(tsp_dummy)

## plot the reordered distance matrix with the dummy cities as lines separating
## the clusters
image(tsp_dummy, tour)
abline(h = which(labels(tour)=="boundary"), col = "red")
abline(v = which(labels(tour)=="boundary"), col = "red")

## plot the original data with paths connecting the points in each cluster
plot(iris[,c(2,3)], col = iris[,5])
paths <- cut_tour(tour, cut = "boundary")
for(p in paths) lines(iris[p, c(2,3)])

## Note: The clustering is not perfect!
}
\references{
Sharlee Climer, Weixiong Zhang (2006): Rearrangement Clustering:
Pitfalls, Remedies, and Applications, \emph{Journal of Machine Learning
Research} \bold{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.
}
\seealso{
Other TSP: 
\code{\link{ATSP}()},
\code{\link{Concorde}},
\code{\link{ETSP}()},
\code{\link{TSPLIB}},
\code{\link{TSP}()},
\code{\link{reformulate_ATSP_as_TSP}()},
\code{\link{solve_TSP}()}
}
\author{
Michael Hahsler
}
\concept{TSP}
\keyword{manip}