6
$\begingroup$

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 :)

$\endgroup$
5
  • 1
    $\begingroup$ It might not make much difference, but it seems to me that making $\theta$ the sum of the lengths of the two longest edges incident on $i$, rather than double the longest, would be slightly tighter and still valid. $\endgroup$
    – prubin
    Dec 8, 2021 at 16:59
  • 1
    $\begingroup$ Hi, thanks for your answer. Yeah i have thought about it before but i wasn't 100% sure it would in fact remain valid and because the gain is rather minimal i stuck to this formulation for now until i got some sort of a proof for any other $\theta$ value. I'm especially curious about a specific example - that i'm unable to find myself - in which $\theta_i$ being the sum of the two incident edges to $i$ in TSP($G$) is not valid. My intuition is somehow telling me that the triangle inequality property should be enough for this bound to hold, but apparently it's not and i just can't picture it $\endgroup$
    – azaryc2s
    Dec 10, 2021 at 12:52
  • 1
    $\begingroup$ If you are going to add the length of the two edges incident on $i$ in the full tour, shouldn't you then subtract the length of the shortest path between their other endpoints? $\endgroup$
    – prubin
    Dec 10, 2021 at 17:14
  • $\begingroup$ Well i am interested in the lower bound for a $TSP(G)$, $G \subset V$ where some $k$ nodes are missing from $V$, right? Naturally we have $TSP(V) \geq TSP(G)$. For the sake of simplicity of this explanation, let's say only one node $i$ is missing and lets have $\theta_i$ be sum of the lengths of its incident edges ( so the edge $(i-1,i)$ and $(i,i+1) )$ in $TSP(V)$. For a single missing node it still holds, that $TSP(V) \geq TSP(G) \geq TSP(V) - \theta_i$. But you cannot simply add the length of the edge $(i-1,i+1)$ to $\theta_i$, because it's not said, that this edge is part of $TSP(G)$ $\endgroup$
    – azaryc2s
    Dec 13, 2021 at 13:43
  • $\begingroup$ You're right, of course. $\endgroup$
    – prubin
    Dec 13, 2021 at 16:47

1 Answer 1

3
$\begingroup$

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)1 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 1 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.

$\endgroup$
1
  • $\begingroup$ Why not just delete the text marked with strikethrough? The revision history will show the original so it isn't lost. $\endgroup$ Feb 9, 2022 at 22:28

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.