# Can this problem be modelled with a transformation from a known TSP with profits?

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?

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