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?
