# How to Model Path Being Only Through Adjacent Cells

I am trying to develop a MILP for a path planning problem. I am operating on a grid of cells that represents a map. The arrangement of cells in the grid represents the placement of the cells in real life on a physical space. I would like to generate a continuous path from cell A to cell B. One constraint that I would like to add is that the solution must be such that the path is only made of transitions between physically adjacent cells. That means no diagonal (or orthogonal) skips over any cells. Only stepping from a cell to its 4 adjacent cells and so on.

How do I add this as a constraint in my problem?

An idea that I had was to make the weight of edge from Cell X to any cell that is not adjacent as infinity, but that seems like a hack in implementation more than a proper constraint.

EDIT: I will be implementing this model using Google OR-Tools, and the weight of all the edges will be elements of an adjacency matrix. Therefore, every possible edge will be a part of the matrix, and hence omiting edges entirely to constraint the solution is not possible. Original question still stands: how can I add this feature of the problem as a constraint?

• I may lack some context, but this looks like a textbook case for A-Star or Dijkstra's Algorithm to me. Jun 6, 2022 at 11:00
• @Rowan It is indeed a similar case. However, I am interested in the MILP formulation of this problem, as I would like to build on it in the future. Thanks. Jun 6, 2022 at 14:32
• Every day is a learning day! I'd never heard of Mixed Integer Programming before today.. I'm intrigued! Jun 6, 2022 at 15:23

A standard approach for modeling a path from source $$s$$ to sink $$t$$ in a directed graph with node set $$N$$ and arc set $$A$$ is to let continuous variable $$x_{ij} \ge 0$$ represent the flow along the arc $$(i,j)$$ from node $$i$$ to node $$j$$ and impose flow-balance constraints $$\sum_{(i,j)\in A} x_{ij} - \sum_{(j,i)\in A} x_{ji} = \begin{cases} 1 & \text{if i=s}\\ -1 & \text{if i=t}\\ 0 &\text{if i\in N \setminus \{s,t\}} \end{cases}$$ that send one unit of flow from $$s$$ to $$t$$. Rather than imposing some large penalty on inadmissible arcs, just omit them from $$A$$.
• @RaghavThakar I think you are missing Rob's point about omitted arcs. Define the arcs so that each connects two adjacent cells. With that, you can't go directly from (2, 3) to (3, 5) because there is no arc between them. The only arcs out of (2, 3) would go to the four adjacent cells $(2 \pm 1, 3 \pm 1).$