I came across a situation in real life that maps to this optimization problem:

Given a fully connected, undirected, weighted graph with $N \ge K$ vertices, find the simple path connecting exactly $K$ vertices with the minimum cost1

My understanding is that when $K=N$ this is the Traveling Salesman Problem. I was initially expecting to find a best approach in the literature, but despite my efforts I was unable to.

Generally for this problem $N \sim 10^2$. Ideally I would like:

  • An exact solution2, if $K \ll N$
  • A good approximation otherwise

I would need my own implementation. Which algorithms / heuristics should I be looking at?

1. Intended as sum of weights on the edges

2. I believe Held-Karp would work for this, but I'm not sure whether there are better approaches I'm not aware of.

  • $\begingroup$ I assume you've looked at the Wikipedia page on the TSP, including algorithms based on ILP? $\endgroup$
    – D.W.
    Commented May 27 at 21:02
  • $\begingroup$ What's your definition for "fully connected" ? $\endgroup$
    – JimN
    Commented May 27 at 21:19
  • $\begingroup$ @JimN, there is an edge between every pair of vertices. $\endgroup$ Commented May 27 at 21:21
  • $\begingroup$ @D.W., Yes, I had looked into that early on, then went on many tangents while researching, I'll review it now. ILP is not a field I'm very familiar with. I have two main concerns: first, I am not sure I understand how to extend the full formulation to my subproblem for non-DP algorithms like Held-Karp; second, I know there exist multiple industrial grade solvers for ILP problems using algorithms like simplex / branch & bound + advanced heuristics, but I'm not sure how well a naïve implementation would do, and I'm not sure how to formulate the problem in OR terms. $\endgroup$ Commented May 27 at 21:43
  • 2
    $\begingroup$ There is a 2-approximation for this problem. The problem is known as $k$-TSP, or sometimes Quota TSP, and is a variant of the prize-collecting TSP; specifically when the prize is unit and the penalty is set to 0. $\endgroup$ Commented May 27 at 21:51


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.