6
$\begingroup$

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. Comparison of acceptable and unacceptable paths

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?

$\endgroup$
3
  • $\begingroup$ I may lack some context, but this looks like a textbook case for A-Star or Dijkstra's Algorithm to me. $\endgroup$
    – Rowan
    Commented Jun 6, 2022 at 11:00
  • 1
    $\begingroup$ @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. $\endgroup$ Commented Jun 6, 2022 at 14:32
  • $\begingroup$ Every day is a learning day! I'd never heard of Mixed Integer Programming before today.. I'm intrigued! $\endgroup$
    – Rowan
    Commented Jun 6, 2022 at 15:23

1 Answer 1

9
$\begingroup$

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$.

$\endgroup$
7
  • $\begingroup$ Thank you. I agree with this, and have already implemented it. However, correct me if I'm wrong, this still allows the path to skip over an adjacent cell without violating the flow-balance constraint. Example: going from cell (2,3) to (3,5) does not violate this constraint, but is not desirable for me. $\endgroup$ Commented Jun 5, 2022 at 20:06
  • $\begingroup$ @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).$ $\endgroup$
    – prubin
    Commented Jun 5, 2022 at 20:51
  • $\begingroup$ @prubin thank you for the clarification. I understand the point now. Quick question: I will be modeling this problem in Google OR Tools, and hence am using an adjacency matrix to represent the arcs. Any way to omit arcs in an adjacency matrix? Setting edge weight to infinity seemed like the only solution. Thanks. $\endgroup$ Commented Jun 5, 2022 at 21:05
  • $\begingroup$ @RaghavThakar Indeed, with OR Tools all arcs are created, and indeed : setting the edge weight to infinity will do the trick. $\endgroup$
    – Kuifje
    Commented Jun 5, 2022 at 21:42
  • $\begingroup$ @Kuifje Thank you for the input. I understand that setting the edge weight to infinity in adjacency matrix will get the desired result. However, I am still wondering if there is a way to add this as a constraint rather than manipulation of the adjacency matrix during implementation. Thanks. $\endgroup$ Commented Jun 6, 2022 at 14:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.