TL;DR: I have to use TSP on a subgraph of size $|V| = n$. I have to construct this subgraph out of a bigger graph. I have to find the subgraph that results in the shortest TSP solution. How to go about this?
Graph $G(V, E)$ is a fully connected mesh in which each node is connected to all other nodes. The edges are of positive non-zero weights. Assume any two nodes $s, t \epsilon V$. The edge from $s$ to $t$ has a different weight than the edge from $t$ to $s$.
Now, for a given $n$, I have to find she shortest simple path that visits at least $n <= |V|$ nodes. This path needs to start and end in a given node $x \epsilon V$. As suggested in this post, I could add a dummy node that is bidirectionally connected to only node $x$ with edge weight 0. This would allow me to use a TSP solver in the special case where $n == |V|$. I read here that the 2-opt method is a suggested method if a good-enough result is appropriate (and it is for me).
However, in the case that $n < |V|$ I have the additional problem that I have to choose the nodes to be visited myself. More specifically, I have to choose the group of nodes that has the shortest TSP solution.
My question to you is, how would you handle the $n < |V|$ case? Maybe TSP is the wrong way to go about it alltogether. To me, the problem I'm facing sounds like a very standard problem in graph theory, but I have so far been unable to find a similar problem.
This is a variant of the prize-collecting TSP problem or optimal subtour problem. A common approach is to introduce binary node variables and dynamically generate generalized subtour elimination constraints (GSECs) only when they are violated.
For a small enough graph, an alternative to dynamic constraint generation is to use the Miller-Tucker-Zemlin formulation.