Interface to travelling salesperson problem solver.
Consider an integer linear programming (ILP) formulation of DFJ (Dantzig et al, 1954) used in this research. Let
minimize
subject to
Constraints (2) and (3) are known as degree constraints indicating that every vertex should be entered and left exactly once correspondingly. Constraints (4) are
subtour elimination constraints that prevent from forming subtours (several unconnected tours on subsets of less than
In the DFJ formulation there are
Here it is proposed to combine heuristics (to get an initial feasible solution) and a linear Diophantine equation (nilde) relaxation to develop a new exact algorithm that constructs all existing optimal solutions for the TSP in an efficient way.
Below is a brief summary of the proposed algorithm.
Step 1. (Initialization) Solve a corresponding assignment problem to obtain an initial lower bound on the value of the optimal TSP solution. Apply heuristics to obtain an initial upper bound.
Step 2. (Subproblem solution) Given the initial lower bound construct all 0-1 solutions to a linear Diophantine equation introduced by Voinov and Nikulin (1997).
Step 3. (Degree constraints check) Remove solutions that do not satisfy the degree constraints.
Step 4. (Subtour elimination) Remove solutions that contain subtours by applying a new simple subtour elimination routine. If there is a solution(s) that contains no subtours, it forms the optimal solution(s): stop. Otherwise, increase the initial lower bound by one and go to step 2. Repeat until the upper bound is reached.
The integer programming formulation of the assignment problem solved in Step 1 of the above algorithm is obtained by relaxing constraints (4), i.e. given by (1) subject to constraints (2), (3) and (5).
For implementing Step 2, solutions of the corresponding subset sum problem should be enumerated. A subset sum problem formulation can be expressed as
Voinon and Nikulin (1997) introduced an algorithm that enumerates all nonnegative integer solutions of equation (6) by using the corresponding generating
function and the binomial theorem.
All
tsp_solver(data, labels=NULL,cluster=0,upper_bound=NULL,
lower_bound=NULL,method="cheapest_insertion",no_go=NULL)
optimal tour(s).
an optimal (minimal) length of the obtained tour(s).
a list of coming feasible tours obtained within [lower_bound, upper_bound]
.
a vector of feasible tour length gone within [lower_bound, upper_bound]
.
a number of feasible tour length gone through
an upper bound of the tour length
a lower bound value of the tour lenght
An n x n
matrix of costs/distances of the TSP (with 0
's or NA
s on the main diagonal). Costs/distances of the unconnected edges must be supplied as NA.
An n
vector of optional city labels. If not given, labels are taken from data
.
Degree constraints can be checked in parallel using parLapply from the parallel package.
cluster
is either 0
(default) for no parallel computing to be used; or 1
for one less than the number of cores; or user-supplied cluster on which to do checking. a cluster here can be some cores of a single machine.
A positive integer, an upper bound of the tour length (cost function), if not supplied (default: NULL
) heuristic solution is obtained using
TSP::solve_TSP(data,method)
.
A positive integer, a lower possible value of the tour lenght (cost function);
if not supplied (default: NULL
), obtained by solving a corresponding assignment problem
using lpSolve::lp.assign(data)
Heuristic method used in TSP::solve_TSP()
(default: cheapest_insertion
)
A suitably large value used in the distance/cost matrix to make related edges infeasible,
if NULL
(default) set to max(data)*10^5
. It can be set to Inf
for TSP()
. However, lpSolve()
is very sensitive to too large values and can result in high values of the lower_bound
.
Vassilly Voinov, Natalya Pya Arnqvist
Voinov, V. and Nikulin, M. (1997) On a subset sum algorithm and its probabilistic and other applications. In: Advances in combinatorial methods and applications to probability and statistics, Ed. N. Balakrishnan, Birkhäuser, Boston, 153-163.
Dantzig, G., Fulkerson, R. and Johnson, S. (1954) Solution of a large-scale traveling-salesman problem. Journal of the operations research society of America , 2(4):393-410.
nilde-package
, get.partitions
, get.knapsack
, get.subsetsum
if (FALSE) {
## some examples...
library(nilde)
set.seed(3)
d <- matrix(sample(1:100,25,replace=TRUE),5,5)
diag(d) <-NA # although no need to specify as the code assumes NAs by default
g <- tsp_solver(d)
g
}
Run the code above in your browser using DataLab