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?

  • $\begingroup$ Out of curiosity, is this a real life problem ? $\endgroup$ – Kuifje Jun 3 '20 at 9:40
  • $\begingroup$ @Kuifje in some sense... solving it would give a bound on a real-life problem. $\endgroup$ – Alberto Santini Jun 3 '20 at 9:41
  • 1
    $\begingroup$ 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)? $\endgroup$ – Kuifje Jun 3 '20 at 9:42
  • $\begingroup$ 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. $\endgroup$ – Alberto Santini Jun 3 '20 at 10:14
  • 1
    $\begingroup$ 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. $\endgroup$ – Alberto Santini Jun 4 '20 at 6:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.