Linear Programming based Reductions for Multiple Visit TSP and Vehicle Routing Problems \title{Linear Programming based Reductions for Multiple Visit TSP and Vehicle Routing Problems
This content will become publicly available on April 9, 2026
Title: Linear Programming based Reductions for Multiple Visit TSP and Vehicle Routing Problems \title{Linear Programming based Reductions for Multiple Visit TSP and Vehicle Routing Problems
The multiple traveling salesman problem (mTSP) is an important variant of metric TSP where a set of k salespeople together visit a set of n cities while minimizing the total cost of the k routes under a given cost metric. The mTSP problem has applications to many real-life problems such as vehicle routing. Rothkopf [14] introduced another variant of TSP called many-visits TSP (MV-TSP) where a request r(v) is given for each city v and a single salesperson needs to visit each city r(v) times and return to his starting point. We note that in MV-TSP the cost of loops is positive, so a TSP solution cannot be trivially extended (without an increase in cost) to a MV-TSP solution by consecutively visiting each vertex to satisfy the visit requirements. A combination of mTSP and MV-TSP, called many-visits multiple TSP (MV-mTSP) was studied by Berczi, Mnich, and Vincze [3] where the authors give approximation algorithms for various variants of MV-mTSP. In this work, we show a simple linear programming (LP) based reduction that converts a mTSP LP-based algorithm to an LP-based algorithm for MV-mTSP with the same approximation factor. We apply this reduction to improve or match the current best approximation factors of several variants of the MV-mTSP. Our reduction shows that the addition of visit requests r(v) to mTSP does not make the problem harder to approximate even when r(v) is exponential in the number of vertices. To apply our reduction, we either use existing LP-based algorithms for mTSP variants or show that several existing combinatorial algorithms for mTSP variants can be interpreted as LP-based algorithms. This allows us to apply our reduction to these combinatorial algorithms while achieving improved guarantees. more »« less
Klein, Nathan; Jin, Billy; Williamson, David P
(, Springer)
Vygen, J; Byrka, J
(Ed.)
One of the most famous conjectures in combinatorial optimization is the four-thirds conjecture, which states that the integrality gap of the subtour LP relaxation of the TSP is equal to $$\frac43$$. For 40 years, the best known upper bound was $1.5$$. Recently, Karlin, Klein, and Oveis Gharan \cite{KKO21b} showed that the max entropy algorithm for the TSP gives an improved bound of $$1.5 - 10^{-36}$. In this paper, we show that the approximation ratio of the max entropy algorithm is at least 1.375, even for graphic TSP. Thus the max entropy algorithm does not appear to be the algorithm that will ultimately resolve the four-thirds conjecture in the affirmative, should that be possible.
Chen, Yu; Kannan, Sampath; Khanna, Sanjeev
(, Leibniz international proceedings in informatics)
We consider the problem of designing sublinear time algorithms for estimating the cost of minimum] metric traveling salesman (TSP) tour. Specifically, given access to a n × n distance matrix D that specifies pairwise distances between n points, the goal is to estimate the TSP cost by performing only sublinear (in the size of D) queries. For the closely related problem of estimating the weight of a metric minimum spanning tree (MST), it is known that for any epsilon > 0, there exists an O^~(n/epsilon^O(1))-time algorithm that returns a (1+epsilon)-approximate estimate of the MST cost. This result immediately implies an O^~(n/epsilon^O(1)) time algorithm to estimate the TSP cost to within a (2 + epsilon) factor for any epsilon > 0. However, no o(n^2)-time algorithms are known to approximate metric TSP to a factor that is strictly better than 2. On the other hand, there were also no known barriers that rule out existence of (1 + epsilon)-approximate estimation algorithms for metric TSP with O^~ (n) time for any fixed epsilon > 0. In this paper, we make progress on both algorithms and lower bounds for estimating metric TSP cost. On the algorithmic side, we first consider the graphic TSP problem where the metric D corresponds to shortest path distances in a connected unweighted undirected graph. We show that there exists an O^~(n) time algorithm that estimates the cost of graphic TSP to within a factor of (2 − epsilon_0) for some epsilon_0 > 0. This is the first sublinear cost estimation algorithm for graphic TSP that achieves an approximation factor less than 2. We also consider another well-studied special case of metric TSP, namely, (1, 2)-TSP where all distances are either 1 or 2, and give an O^~(n ^ 1.5) time algorithm to estimate optimal cost to within a factor of 1.625. Our estimation algorithms for graphic TSP as well as for (1, 2)-TSP naturally lend themselves to O^~(n) space streaming algorithms that give an 11/6-approximation for graphic TSP and a 1.625-approximation for (1, 2)-TSP. These results motivate the natural question if analogously to metric MST, for any epsilon > 0, (1 + epsilon)-approximate estimates can be obtained for graphic TSP and (1, 2)-TSP using O^~ (n) queries. We answer this question in the negative – there exists an epsilon_0 > 0, such that any algorithm that estimates the cost of graphic TSP ((1, 2)-TSP) to within a (1 + epsilon_0)-factor, necessarily requires (n^2) queries. This lower bound result highlights a sharp separation between the metric MST and metric TSP problems. Similarly to many classical approximation algorithms for TSP, our sublinear time estimation algorithms utilize subroutines for estimating the size of a maximum matching in the underlying graph. We show that this is not merely an artifact of our approach, and that for any epsilon > 0, any algorithm that estimates the cost of graphic TSP or (1, 2)-TSP to within a (1 + epsilon)-factor, can also be used to estimate the size of a maximum matching in a bipartite graph to within an epsilon n additive error. This connection allows us to translate known lower bounds for matching size estimation in various models to similar lower bounds for metric TSP cost estimation.
Jin, Billy; Klein, Nathan; Williamson, David P.
(, Lecture notes in computer science)
Del Pia, Alberto; Kaibel, Volker
(Ed.)
A long-standing conjecture for the traveling salesman problem (TSP) states that the integrality gap of the standard linear programming relaxation of the TSP (sometimes called the Subtour LP or the Held-Karp bound) is at most 4/3 for symmetric instances of the TSP obeying the triangle inequality. In this paper we consider the half-integral case, in which a feasible solution to the LP has solution values in {0,1/2,1} . Karlin, Klein, and Oveis Gharan [9], in a breakthrough result, were able to show that in the half-integral case, the integrality gap is at most 1.49993; Gupta et al. [6] showed a slight improvement of this result to 1.4983. Both of these papers consider a hierarchy of critical tight sets in the support graph of the LP solution, in which some of the sets correspond to cycle cuts and the others to degree cuts. Here we show that if all the sets in the hierarchy correspond to cycle cuts, then we can find a distribution of tours whose expected cost is at most 4/3 times the value of the half-integral LP solution; sampling from the distribution gives us a randomized 4/3-approximation algorithm. We note that known bad cases for the integrality gap have a gap of 4/3 and have a half-integral LP solution in which all the critical tight sets in the hierarchy are cycle cuts; thus our result is tight.
Gutekunst, Samuel C.; Williamson, David P.
(, Mathematics of Operations Research)
null
(Ed.)
The traveling salesman problem (TSP) is a fundamental problem in combinatorial optimization. Several semidefinite programming relaxations have been proposed recently that exploit a variety of mathematical structures including, for example, algebraic connectivity, permutation matrices, and association schemes. The main results of this paper are twofold. First, de Klerk and Sotirov [de Klerk E, Sotirov R (2012) Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry. Math. Programming 133(1):75–91.] present a semidefinite program (SDP) based on permutation matrices and symmetry reduction; they show that it is incomparable to the subtour elimination linear program but generally dominates it on small instances. We provide a family of simplicial TSP instances that shows that the integrality gap of this SDP is unbounded. Second, we show that these simplicial TSP instances imply the unbounded integrality gap of every SDP relaxation of the TSP mentioned in the survey on SDP relaxations of the TSP in section 2 of Sotirov [Sotirov R (2012) SDP relaxations for some combinatorial optimization problems. Anjos MF, Lasserre JB, eds., Handbook on Semidefinite, Conic and Polynomial Optimization (Springer, New York), 795–819.]. In contrast, the subtour linear program performs perfectly on simplicial instances. The simplicial instances thus form a natural litmus test for future SDP relaxations of the TSP.
We consider a variant of the vehicle routing problem (VRP) where each customer has a unit demand and the goal is to minimize the total cost of routing a fleet of capacitated vehicles from one or multiple depots to visit all customers. We propose two parallel algorithms to efficiently solve the column-generation-based linear-programming relaxation for this VRP. Specifically, we focus on algorithms for the “pricing problem,” which corresponds to the resource-constrained elementary shortest path problem. The first algorithm extends the pulse algorithm for which we derive a new bounding scheme on the maximum load of any route. The second algorithm is based on random coloring from parameterized complexity which can be also combined with other techniques in the literature for improving VRPs, including cutting planes and column enumeration. We conduct numerical studies using VRP benchmarks (with 50–957 nodes) and instances of a medical home care delivery problem using census data in Wayne County, Michigan. Using parallel computing, both pulse and random coloring can significantly improve column generation for solving the linear programming relaxations and we can obtain heuristic integer solutions with small optimality gaps. Combining random coloring with column enumeration, we can obtain improved integer solutions having less than 2% optimality gaps for most VRP benchmark instances and less than 1% optimality gaps for the medical home care delivery instances, both under a 30-minute computational time limit. The use of cutting planes (e.g., robust cuts) can further reduce optimality gaps on some hard instances, without much increase in the run time. Summary of Contribution: The vehicle routing problem (VRP) is a fundamental combinatorial problem, and its variants have been studied extensively in the literature of operations research and computer science. In this paper, we consider general-purpose algorithms for solving VRPs, including the column-generation approach for the linear programming relaxations of the integer programs of VRPs and the column-enumeration approach for seeking improved integer solutions. We revise the pulse algorithm and also propose a random-coloring algorithm that can be used for solving the elementary shortest path problem that formulates the pricing problem in the column-generation approach. We show that the parallel implementation of both algorithms can significantly improve the performance of column generation and the random coloring algorithm can improve the solution time and quality of the VRP integer solutions produced by the column-enumeration approach. We focus on algorithmic design for VRPs and conduct extensive computational tests to demonstrate the performance of various approaches.
Pillia, A, and Singh, M. Linear Programming based Reductions for Multiple Visit TSP and Vehicle Routing Problems \title{Linear Programming based Reductions for Multiple Visit TSP and Vehicle Routing Problems. Retrieved from https://par.nsf.gov/biblio/10613753.
Pillia, A, & Singh, M. Linear Programming based Reductions for Multiple Visit TSP and Vehicle Routing Problems \title{Linear Programming based Reductions for Multiple Visit TSP and Vehicle Routing Problems. Retrieved from https://par.nsf.gov/biblio/10613753.
Pillia, A, and Singh, M.
"Linear Programming based Reductions for Multiple Visit TSP and Vehicle Routing Problems \title{Linear Programming based Reductions for Multiple Visit TSP and Vehicle Routing Problems". Country unknown/Code not available: Arxiv. https://par.nsf.gov/biblio/10613753.
@article{osti_10613753,
place = {Country unknown/Code not available},
title = {Linear Programming based Reductions for Multiple Visit TSP and Vehicle Routing Problems \title{Linear Programming based Reductions for Multiple Visit TSP and Vehicle Routing Problems},
url = {https://par.nsf.gov/biblio/10613753},
abstractNote = {The multiple traveling salesman problem (mTSP) is an important variant of metric TSP where a set of k salespeople together visit a set of n cities while minimizing the total cost of the k routes under a given cost metric. The mTSP problem has applications to many real-life problems such as vehicle routing. Rothkopf [14] introduced another variant of TSP called many-visits TSP (MV-TSP) where a request r(v) is given for each city v and a single salesperson needs to visit each city r(v) times and return to his starting point. We note that in MV-TSP the cost of loops is positive, so a TSP solution cannot be trivially extended (without an increase in cost) to a MV-TSP solution by consecutively visiting each vertex to satisfy the visit requirements. A combination of mTSP and MV-TSP, called many-visits multiple TSP (MV-mTSP) was studied by Berczi, Mnich, and Vincze [3] where the authors give approximation algorithms for various variants of MV-mTSP. In this work, we show a simple linear programming (LP) based reduction that converts a mTSP LP-based algorithm to an LP-based algorithm for MV-mTSP with the same approximation factor. We apply this reduction to improve or match the current best approximation factors of several variants of the MV-mTSP. Our reduction shows that the addition of visit requests r(v) to mTSP does not make the problem harder to approximate even when r(v) is exponential in the number of vertices. To apply our reduction, we either use existing LP-based algorithms for mTSP variants or show that several existing combinatorial algorithms for mTSP variants can be interpreted as LP-based algorithms. This allows us to apply our reduction to these combinatorial algorithms while achieving improved guarantees.},
journal = {},
publisher = {Arxiv},
author = {Pillia, A and Singh, M},
}
Warning: Leaving National Science Foundation Website
You are now leaving the National Science Foundation website to go to a non-government website.
Website:
NSF takes no responsibility for and exercises no control over the views expressed or the accuracy of
the information contained on this site. Also be aware that NSF's privacy policy does not apply to this site.
An official website of the United States government
