I'm having some trouble trying to formulate the integer program for the following instance of the travelling salesman problem.
Well, it is not quite a TSP, for it does not need for all nodes to be visited. In fact, an accepted solution is to visit only the starting node, although it may not be the objective solution.
The ideia is to find a route that maximizes the profit for a given graph with costs in the edges and profit in the vertices, while also returning to the origin vertex.
The instance: A complete graph $G = (V,E)$ with costs $c_e, e\in E$, between the vertices, profit $p_v, v \in V$, for each vertex and an origin vertex $v_o$.
The solution: A route $R=(v_o,v_1,v_2,\ldots,v_k,v_o)$ starting in $v_o$ with $k$ intermediate vertices $v_i \in V$, then returning to $v_o$. Each vertex in $V\setminus{v_o}$ can be contained only once in $R$.
The objective: To maximize the total value $v(R)=\sum_{i=1}^k{p_v}_i - (c_{v_o,v_1} + \sum_{i=1}^{k-1} c_{v_i,v_{i+1}} + c_{v_k,v_o})$
Any insight will be appreciated.
Ok, so, with the help of an article found and provide by @dbal, I could formulate the following:
\begin{alignat*}{2} & \text{maximize: } &\sum_{i=1}^n \sum_{j=1}^n p_ix_{ij} - \sum_{i=1}^n \sum_{j=1}^n c_{ij}x_{ij}& &\\ & \text{subject to: } & \sum_{j=2}^n x_{1j} = 1 \tag1\\ & & \sum_{j=1}^n x_{ij} \leq 1 & \quad \forall i \in V \tag2\\ & & \sum_{i=1}^n x_{ij} - \sum_{k=1}^n x_{jk} = 0 & \quad \forall j \in V \tag3\\ & & \sum_{i \in S} \sum_{j \in S} x_{ij} \leq |S|-1 & \quad \forall S \subset V \setminus \{1\} \tag4\\ & & x_{ij} \in \{0,1\} & \quad \forall i \in V, \forall j \in V \tag5\\ & & c_{ij},p_{i} \ge 0 & \quad \forall i \in V, \forall j \in V \tag6 \end{alignat*}
Validations would be greatly appreciated.