Building a Partial Tour

A user on Mathematics Stack Exchange posted a question that, while superficially similar to the prize collecting traveling salesman problem (TSP), also has substantial differences to it. You are given a rectangular grid where each cell contains a reward. The objective is to build a tour of some (but not all) cells, with movement restricted to adjacent cells (those sharing an edge with the current cell), subject to the restriction that you cannot visit two cells with identical rewards. The objective is to maximize the value of the cells visited. It differs from the prize collecting TSP in several ways:

• there is no designated start/end cell for the tour;
• there are no edge costs (movement incurs no objective penalty);
• there is no penalty for unvisited cells; and of course
• duplicate rewards are prohibited.

A key part of the user's question was how to handle subtour elimination. The user was looking at the classic Miller-Tucker-Zemlin (MTZ) approach for TSPs, which involves an auxiliary variable at each cell recording in essence the position of the cell (first, second, ...) in the tour. The implementation of MTZ involves constraints at each cell except the depot (tour origin/destination). In the current problem, there is not designated depot, and you cannot just pick a cell to serve as the depot because you do not know which cells will be in the optimal tour.

The workaround I suggested in a reply to the post is to add an artificial cell (the "depot"), connected to every cell in the original grid, and use that to implement the MTZ constraints. The one mildly tricky part is that the cell immediately preceding the depot and the cell immediately following the depot in the tour need to be adjacent (or the same, if the tour only visits one cell). That is easily handled at the cost of some extra constraints.

Assume the grid contains $m$ rows and $n$ columns. Let us start by numbering the cells $1,\dots,mn$ in raster scan order from upper left to lower right, and call the depot cell 0. Let $r_i$ denote the reward for visiting cell $i$ and $N_i$ denote the set of cells (including the depot) adjacent to cell $i$. Finally, let $R$ denote the set of possible rewards and $C_r$ the "cluster" of cells having the same reward $r\in R.$ We build the model as follows.

Variables

• $x_{ij}\in \{0,1\}$ will be 1 if the tour moves from cell $i$ to cell $j,$ 0 otherwise. 

• $y_{i} \in \{0,1\}$ will be 1 if the tour visits cell $i > 0,$ 0 if not.

• $z_{i} \ge 0$ is the auxiliary variable (position) for cell $i$ in the MTZ constraints (indexing where cell $i$ falls in the tour). 

If cell $i$ does not appear in the tour, the value of $z_{i}$ will be irrelevant (and the solver will likely set it to 0).

 

Objective

The objective is to maximize $$\sum_{i} r_i y_i.$$ 

 

Constraints

• Movements may only occur between adjacent cells (with the depot cell adjacent to every other cell).  $$x_{ij} = 0 \quad \forall i, \forall j\notin N_i.$$

 

• The depot must be exited and entered exactly once. $$\sum_{i > 0} x_{0i} = 1 = \sum_{i > 0} x_{i0}.$$

 

• Each cell other than the depot is entered and exited once if visited and zero times if not visited. $$\sum_{j} x_{ji} = y_i = \sum_{j} x_{ij} \quad \forall i>0.$$

 

• At most one cell with a given reward value can be visited. $$\sum_{i\in C_r} y_i \le 1 \quad \forall r\in R.$$

 

• MTZ: If the tour moves from cell $i$ to cell $j,$ the position value for cell $j$ must be at least one greater than the position value for cell $i$ (excluding $j=0,$ i.e., return to depot). $$x_{ij} = 1 \implies z_j \ge z_i + 1 \quad \forall i, \forall j > 0.$$

 

• If the tour goes $0 \rightarrow i \rightarrow \dots \rightarrow j \rightarrow 0,$ then cells $i$ and $j$ must be adjacent (or the same). $$x_{0i} + x_{j0} \le 1 \quad \forall i>0, j>0, i\neq j, j \notin N_i.$$

 

I tested the code on the example in the Math SE post, using Java and the FICO XpressMP MIP solver, and it produced what appears to be an optimal tour (confirmed by the original poster) in about two minutes on my somewhat archaic desktop. I posted the tour in a comment to my answer to the original question. The Java code is available (Creative Commons 4 open source license) from my Git repository.