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)