How to build a contiguous path?

Question

In my (simplified) problem I have a grid. Given an origin cell, I'd like to find a minimum-length path on this grid that connects to one or more target cells.

My idea is to use a series of binary variables has_path to indicate which cells have a path build on them.

A second set of binary variables i_can_reach_entrance constrains the problem such that i_can_reach_entrance[y, x] can only be true if a path is built at (y, x) and i_can_reach_entrance is true for one of (y,x)'s neighbours.

Unfortunately, these constraints don't induce my program (included as an MWE, below) to build paths.

There are easier ways to solve this than with integer programming, of course, but this is my preferred method as the pathing will be integrated with a more complex program.

Any thoughts on how to appropriately enforce contiguity would be welcome.

#!/usr/bin/env python3

from typing import Final, List, Tuple

import cvxpy as cp
import numpy as np

WIDTH: Final[int] = 16
HEIGHT: Final[int] = 16

DXDY: Final[List[Tuple[int, int]]] = [(-1, 0), (1, 0), (0, -1), (0, 1)]

constraints = []

# A binary variable indicating whether we build a path at location (i, j)
has_path = cp.Variable((HEIGHT, WIDTH), boolean=True)

# Set a target cell (note: there could be more than one)
row_temp = [False] * WIDTH
row_temp[6] = True
constraints.append(has_path[0,:] == np.array(row_temp))

# Try to ensure contiguity
i_can_reach_entrance = cp.Variable((HEIGHT, WIDTH), boolean=True)
for y in range(HEIGHT):
  for x in range(WIDTH):
    if not (y==HEIGHT-1 and x==1):
      # Build the disjunction n_can_reach = icre[NORTH] v icre[SOUTH] v icre[EAST] v icre[WEST]
      num_reaching_neighbours = 0
      n_can_reach = cp.Variable(boolean=True)
      for dx, dy in DXDY:
        nx = x + dx
        ny = y + dy
        # Don't look outside the grid
        if ny<0 or nx<0 or ny==HEIGHT or nx==WIDTH:
          continue
        constraints.append(n_can_reach >= i_can_reach_entrance[ny, nx])
        num_reaching_neighbours += i_can_reach_entrance[ny,nx]
      constraints.append(n_can_reach <= num_reaching_neighbours)

      # n_can_reach is now true if any neighbour can reach the entrance

      # We can only reach the entrance if one of our neighbours can and we build
      # a path at our location
      constraints.append(i_can_reach_entrance[y, x] <= has_path[y,x])
      constraints.append(i_can_reach_entrance[y, x] <= n_can_reach)
      constraints.append(i_can_reach_entrance[y, x] + 1 >= n_can_reach + has_path[y,x])
    else:
      # Seed the path by specifying an origin cell
      constraints.append(i_can_reach_entrance[HEIGHT-1,1]==True)


# Set up the problem
objective = cp.Minimize(cp.sum(has_path))
problem = cp.Problem(objective, constraints)

sol = problem.solve(solver='CBC', maximumSeconds=120, verbose=True)

print(f"Optimized value = {sol}")

print("Has path:")
print(has_path.value)

print("Can I reach the entrance?")
print(i_can_reach_entrance.value)

Answer 1

For simplicity, let binary variable $c_{i,j}$ indicate whether cell $(i,j)$ can reach the entrance, and let binary variable $p_{i,j}$ indicate whether cell $(i,j)$ has a path built. Necessary conditions are $$c_{i,j}\implies p_{i,j}$$ and $$c_{i,j}\implies \left(c_{i-1,j}\lor c_{i+1,j} \lor c_{i,j-1} \lor c_{i,j+1}\right),$$ both of which yield linear constraints. But these do not prevent subtours.

One way to repair this approach is to include a third index $k$ that represents the number of steps taken: $$c_{i,j,k}\implies p_{i,j}$$ and $$c_{i,j,k}\implies \left(c_{i-1,j,k-1}\lor c_{i+1,j,k-1} \lor c_{i,j-1,k-1}\lor c_{i,j+1,k-1}\right)$$