Return to Answer

Introduce a dummy depot (adjacent only to the "border" cells in the first or last row or column) and send one unit of flow from the depot to each black square. Let nonnegative decision variable $x_{i,j}$ represent the flow along the directed arc from node $i$ to node $j$, and let binary decision variable $y_k$ indicate whether node $k$ is part of the red route. Let $B$ be the number of black cells. To prevent trapped black cells, you need flow balance constraints along with big-M constraint $$x_{i,j} \le B(1 - y_j) \quad \text{for all $(i,j)$},$$ which enforces $x_{i,j} > 0 \implies y_j = 0$.

For your example instance, the optimal objective value turns out to be $33$.

Introduce a dummy depot (adjacent only to the "border" cells in the first or last row or column) and send one unit of flow from the depot to each banned cell. Let nonnegative decision variable $z_{i,j}$ represent the flow along the directed arc from node $i$ to node $j$, and let binary decision variable $y_k$ indicate whether node $k$ is part of the loop. Let $B$ be the number of banned cells. To prevent trapping banned cells, you need flow balance constraints along with big-M constraint $$z_{i,j} \le B(1 - y_j) \quad \text{for all $(i,j)$},$$ which enforces $z_{i,j} > 0 \implies y_j = 0$.

For your example instance, the maximum score turns out to be $33$:

Introduce a dummy depot (adjacent only to the "border" cells in the first or last row or column) and send one unit of flow from the depot to each black square. Let nonnegative decision variable $x_{i,j}$ represent the flow along the directed arc from node $i$ to node $j$, and let binary decision variable $y_k$ indicate whether node $k$ is part of the red route. Let $B$ be the number of black cells. To prevent trapped black cells, you need flow balance constraints along with the following: \begin{align} x_{i,j} &\le B(1 - y_i) && \text{for all $(i,j)$} \tag1 \\ x_{i,j} &\le B(1 - y_j) && \text{for all $(i,j)$} \tag2 \end{align} Constraints $(1)$ and $(2)$ enforce $(y_i \lor y_j) \implies x_{i,j} = 0$.

Introduce a dummy depot (adjacent only to the "border" cells in the first or last row or column) and send one unit of flow from the depot to each black square. Let nonnegative decision variable $x_{i,j}$ represent the flow along the directed arc from node $i$ to node $j$, and let binary decision variable $y_k$ indicate whether node $k$ is part of the red route. Let $B$ be the number of black cells. To prevent trapped black cells, you need flow balance constraints along with big-M constraint $$x_{i,j} \le B(1 - y_j) \quad \text{for all $(i,j)$},$$ which enforces $x_{i,j} > 0 \implies y_j = 0$.

For your example instance, the optimal objective value turns out to be $33$.

Introduce a dummy depot and send one unit of flow from the depot to each black square. Let nonnegative decision variable $x_{i,j}$ represent the flow along the directed arc from node $i$ to node $j$, and let binary decision variable $y_k$ indicate whether node $k$ is part of the red route. Let $B$ be the number of black cells. To prevent trapped black cells, you need flow balance constraints along with the following: \begin{align} x_{i,j} &\le B(1 - y_i) && \text{for all $(i,j)$} \tag1 \\ x_{i,j} &\le B(1 - y_j) && \text{for all $(i,j)$} \tag2 \end{align} Constraints $(1)$ and $(2)$ enforce $(y_i \lor y_j) \implies x_{i,j} = 0$.

Introduce a dummy depot (adjacent only to the "border" cells in the first or last row or column) and send one unit of flow from the depot to each black square. Let nonnegative decision variable $x_{i,j}$ represent the flow along the directed arc from node $i$ to node $j$, and let binary decision variable $y_k$ indicate whether node $k$ is part of the red route. Let $B$ be the number of black cells. To prevent trapped black cells, you need flow balance constraints along with the following: \begin{align} x_{i,j} &\le B(1 - y_i) && \text{for all $(i,j)$} \tag1 \\ x_{i,j} &\le B(1 - y_j) && \text{for all $(i,j)$} \tag2 \end{align} Constraints $(1)$ and $(2)$ enforce $(y_i \lor y_j) \implies x_{i,j} = 0$.