4

The profitable tour problem (PTP) is defined on a graph $G=(V,E)$ with $|V|=n$, where each vertex $i \in V$ has an associated prize $m_i \geq 0$ and each edge $e \in E$ has an associated cost $c_e \geq 0$. The problem asks to find a subset of vertices and a tour visiting them, maximising the difference between prizes collected and travel costs paid. Let $\mathbf{y} \in \{0,1\}^n$ be a vector whose $i$-th entry is 1 iff vertex $i \in V$ is included in the tour, and let $\text{TSP}(\mathbf{y})$ denote the cost of the shortest tour over the vertices included by $\mathbf{y}$. Furthermore denote the vector of profits as $\mathbf{m} = (m_1, \ldots, m_n)$. Then one can write the PTP as:

$$ \max_{\mathbf{y} \in \{0,1\}^n} \big\{ \mathbf{m}^\intercal \mathbf{y} - \text{TSP}(\mathbf{y}) \big\}$$

I have a problem which is, in some informal sense, dual to the PTP. My problem can be written as follows:

$$ \max_{\mathbf{y} \in \{0,1\}^n} \big\{ \text{TSP}(\mathbf{y}) - \mathbf{m}^\intercal \mathbf{y} \big\}$$

In other words, I am looking for a subset of vertices of $V$ over which the shortest tour is longest but, to include a vertex $i$ in my tour, I have to pay a penalty $m_i$.

I have been thinking about it for a while, but I feel like the opposite optimisation direction between the outer maximisation problem and the inner minimisation (hidden in $\text{TSP}$) makes it hard to tackle this problem simply with a transformation from an existing TSP with profits, such as the PTP.

Am I missing something obvious? Is there a straightforward transformation to a well-known problem that I don't see?

Alberto Santini
  • 2,113
  • 9
  • 23
  • Out of curiosity, is this a real life problem ? – Kuifje Jun 03 '20 at 09:40
  • @Kuifje in some sense... solving it would give a bound on a real-life problem. – Alberto Santini Jun 03 '20 at 09:41
  • 1
    I need some time to think about it, but have you thought of transformation from a known TSP by setting the costs $c_{ij}$ to $-c_{ij}$ (in order to have a min TSP problem)? – Kuifje Jun 03 '20 at 09:42
  • Initially I thought about that, but I discarded the idea because I thought it was bound to find longest tours in the inner TSP problem, not shortest. I might be wrong, though... I will think more about it. – Alberto Santini Jun 03 '20 at 10:14
  • There is literature on the MAX TSP ... i mean the "taxicab rip off problem" (see https://www.researchgate.net/publication/227191741_The_Maximum_TSP) – user3680510 Jun 03 '20 at 10:37
  • @user3680510: exactly. I think swapping the sign on edge costs as proposed by Kuifje would lead me to a MaxTSP, which is not what I am trying to solve. I might be missing something in Kuifje's reasoning, though. – Alberto Santini Jun 03 '20 at 10:45
  • @AlbertoSantini Nope this was my (possibly bad) idea indeed ! But are you 100% sur that a MaxTSP isn't what you're looking for ? Is it because of the penalties ? – Kuifje Jun 03 '20 at 10:50
  • If it is a directed graph you can just add the m values to all incoming edges. – PSLP Jun 03 '20 at 10:56
  • Something is unclear to me. Do you have some sort of TSP solver and would like to use it to solve your problem ? Or are you trying to show a reduction from one problem to another for complexity theory ? – Kuifje Jun 03 '20 at 12:16
  • So, I would say it's not a MaxTSP because you still want to find the shortest tour over the vertices that you visit, not the longest one. Second, I would like to explore reductions to the TSP to, e.g., use Concorde to solve this problem or, otherwise, to make sure I don't start working on it just to realise at the end that a simple transformation would have turned it into an already well-known problem. For example, if it turns out to be a PTP then you can use well-known transformations PTP -> ATSP and then ATSP -> TSP and give it to Concorde. – Alberto Santini Jun 03 '20 at 12:51
  • 1
    I understand the confusion might have arisen from me using the "longest TSP" terminology. I didn't mean that the problem asks for the longest hamiltonian tour. I edited the question and I hope it's clearer now. – Alberto Santini Jun 04 '20 at 06:39
  • So in a way it is a $\max \min $ TSP right ? There are some articles for the $\min \max $ TSP, for example here : https://www.sciencedirect.com/science/article/pii/S0166218X03005493 . But still quite not your problem. – Kuifje Jun 04 '20 at 09:42
  • @Kuifje Correct. From a cursory look to the min max TSP paper I also agree that it doesn't look much like this problem. Maybe it is, in the end, novel and not easy to transform into a known problem. – Alberto Santini Jun 04 '20 at 15:05
  • Maybe you could try on mathoverflow if nobody is inspired here. But if nobody has answered, probably, to answer your question: no, you are not missing something obvious! Sounds tricky – Kuifje Jun 04 '20 at 16:01

0 Answers0