Lower bounds for TSP with k missing nodes

Question

I'm struggling with this question for several weeks already and seem to be either stuck, or the bound is not going to be any better. Let's jump right into the problem:

Given a standard TSP on a graph $G$ with $n$ nodes where the triangle inequality holds, let's consider $L_g$ to be the length of the TSP-Tour on this graph. Now let's consider $H \subseteq G$ to be a subgraph, in which $0 \leq k \leq n-1$ nodes are missing and $L_h$ being the TSP-length on $H$. We can derive a lower bound for $L_h$ like this: $$ L_h \geq L_g - \sum_{i \in G}(1-Y_i)\theta_i $$ where $Y_i=1$ when $i \in H$ and $Y_i=0$ when $i \notin H$ and $\theta_i=2 \cdot \max_{\forall j \in G}(c_{ij})$, where $c_{ij}$ is the length of the edge $(i,j)$

So what we basically do here is say, that for each node, that is in $G$ but not in $H$ anymore, we subtract two times the longest edge incident to this node ($\theta_{i}$ represents that value) from $L_g$ and get a lower bound for $L_h$. This seems to be valid, although rather a poor bound.

Hence my question: does anybody know or has any idea, how we can shrink $\theta_{i}$ in value by which the bound gets tighter? This should be done without increasing the number of inequalities and for any arbitrary number $k$ of "missing" nodes.

Edit1: I should point out, that i experimentally tried out some other values for $\theta_i$ like simply adding the length of the edge leading to $i$ and away from $i$ in the TSP-tour in $G$. Although i still cannot find a decent example of why it would not hold, it was cutting off otherwise optimal solutions, so i simply accepted that it is wrong :)

Answer 1

There is less suggestions than I was hoping for, but I guess it's fine, since I finally came up with some ideas of my own, so I figured I'll post it here - maybe someone might need it some day.

A little bit of background before the answer: Basically the inequality comes from the work of Tran et al. (2016)¹ on the Unrelated Parallel Machine Scheduling Problem with Sequence-Dependent Setup-Times. There it was used to cut off invalid solutions in their benders-decomposition approach (more exactly branch-and-check). Because of the nature of the problem, they were able to calculate and prove a much tighter $\theta$ value, which resulted in very good cuts. Now I am trying to apply their approach to a different, but similar problem. The difference is, I have a symmetric graph on a Cartesian plane and my nodes have no "processing time" which I can use for $\theta$.

--- Edit: I leave this part here for the sake of completeness - for the correct answer please refrain to my edit further below ---

I figured though, that what i can do, is to transform my graph into an asymmetric version, then define a pseudo "process time" for each node, as it's minimum length of the incoming arc, and define the lengths of the outgoing arcs from $i$ as $c((i,k)) = p_i + s_{ik}$ and since i got the lengths of the original edges and the values $p$ for each node, i can also calculate $s_{ik}$. Now that i have the values, i can simply apply their calculation of $\theta$ $$ \theta_{i} = p_{i} + \max S_{i} $$ where $\max S_{i}$ is the maximum value of $s_{ki} \forall k \in G$ and rely on their proof for the validity. All that's left is to prove, that my transformation is correct and bidirectional. This is something i still have to do, but before i am bothered, i ran some tests on few instances and the cuts do not seem to cut off any valid solutions so far. i might edit the answer in the future to provide more detailed explanation (with some graph-examples maybe) when i find the time for :)

If by any chance, anyone spots any inconsistency or problems with this approach, i would very much appreciate the feedback!

EDIT: Well i did in fact myself spot the problem with this approach. Given that this process times are pseudo and depend on whether some edge is still in the graph, this doesn't work for the cuts and hence also for the lower bound. It basically only holds for a subgragh with exactly 1 fewer node. I did come up with tighter bounds though. I figured: why transforming my graph to the other problem using pseudo process times - i already have that problem, only that my process times are all 0 and all i got are sequence-dependent setup-times. So $p_{i} = 0$ and $max(S_{i})$ is the longest edge adjacent to $i$. There is something missing though - and that's $min(S_{i})$, the shortest edge adjacent to $i$. This is 0 in case of ¹ because the depot is fictional and has no final setup-time so the edge to it is $0$ from any node. To my understanding the complete equation for $\delta_{i}$ should be:

$$ \theta_{i} = p_{i} + \max_{j \in G} (c_{ji}) + \min_{j \in G} (c_{ij}) $$

---

_Reference

_{[1] Tran, T. T., Araujo, A., Beck, J. C. (2016). Decomposition methods for the parallel machine scheduling problem with setups. INFORMS Journal on Computing. 28(1):83-95.}