Tutorial 4: Variable and constraint filtering (Shortest Path)

The input to the shortest path problem is a set of nodes $N$ and a distance matrix, with $d_{ij}$ the distance between node $i \in N$ and $j \in N$ . The objective is to find a shortest path between an origin and destination – for the example below it is node 1 and node 6, respectively.

The following formulation of the shortest path is based on a complete directed graph. That is, it assumes that there are links between every pair of nodes and that the distance matrix is populated accordingly. In practice, if there is no link between any pair of nodes (e.g. there is no direct road between two cities), the distance is typically set to infinity. Furthermore, the links between the nodes have direction – we refer to these as arcs. In practice, this is useful to accommodate road networks which may contain one-way traffic.

Let the binary decision variable $x_{ij}$ take on a value of 1 if arc $(i,j)$ is included in the shortest path route. In the formulation of the shortest path problem below, the constants $o$ and $d$ are used for the indices of the origin and destination nodes, respectively.

\text{minimize}~ \sum\limits_{i \in N}{ \sum\limits_{j \in N \setminus\{i\} }{d_{ij} x_{ij}}} \\ \sum_{j \in N\setminus \{i\}}{x_{ij}} - \sum_{j \in N\setminus \{i\}}{x_{ji}} = \begin{cases} 1 & i=o \\ -1 & i=d\\ 0 & \text{otherwise} \end{cases},\quad \forall i \in N

For the purpose of this example, let us assume a road network with 4 nodes. Then, the node index set is defined as

set N = {1,2,3,4}

and the distance matrix is

const d = { {0, 2, infty, 11}, 
            {2, 0, 3, 8}, 
            {6, 3, 0, 4}, 
            {11, 8, 4, 0} }, forall i in N, forall j in N

Since the formulation we use is based on a complete input graph, any link that does not exist, e.g. there is no direct road between the two cities, are accommodated by assuming an infinite value for the distance. For our example, there is no direct link between nodes 1 and 3, therefore a value of $\infty$ is assigned to $d_{1,3}$ in the above distance matrix by using the infty keyword.

A binary decision variable is associated with each arc $(i,j)$ ,

bin x, forall i in N, forall j in N

The objective is to find the shortest path – this is accomplished by

min sum_{i in N}{ sum_{j in N setminus {i}}{ d_{i,j}*x_{i,j} }}

There is an important syntax feature to take note of – to ignore the symmetric variables $x_{ii}$ , we make use of the set minus operator “\” to remove the index $i$ from the second summation, since it forms part of the outer summation. Mathematically, this will be displayed as $\sum_{j \in N \setminus \{i\}}$ .

Next, we need to deal with the following set of constraints:

\sum_{j \in N \setminus \{i\}}{x_{ij}} - \sum_{j \in N\setminus \{i\}}{x_{ji}} = \begin{cases} 1 & i=o \\ -1 & i=d\\ 0 & \text{otherwise} \end{cases},\quad \forall i \in N

These are referred to as the flow balancing constraints ensuring that for each node $i \in N$ that is not an origin or destination, the total flow out of the node is equal to the total flow into the node. If node $i \in N$ is the origin, then the sum of the outbound flow is set to 1. If node $i \in N$ is the destination, then the sum of the inbound flow is set to -1.

Since we decided to make node 1 the origin and node 4 the destination, the above constraints are written explicitly as

\sum\limits_{j \in N\setminus \{1\}}{x_{1,j}}- \sum\limits_{j \in N\setminus \{1\}}{x_{j,1}}=1 \\ \sum\limits_{j \in N\setminus \{i\}}{x_{i,j}}- \sum\limits_{j \in N\setminus \{i\}}{x_{j,i}}=0,\qquad\forall i \in N \setminus \{1,4 \} \\ \sum\limits_{j \in N\setminus \{4\}}{x_{4,j}}- \sum\limits_{j \in N\setminus \{4\}}{x_{j,4}}=-1

The code listing for this is then

constr sum_{j in N setminus {1} }{ x_{1,j} } - sum_{j in N setminus {1} }{ x_{j,1} } = 1
constr sum_{j in N setminus {i} }{ x_{i,j} } - sum_{j in N setminus {i} }{ x_{j,i} } = 0, forall i in N setminus {1,4}
constr sum_{j in N setminus {4} }{ x_{4,j} } - sum_{j in N setminus {4} }{ x_{j,4} } = -1

Take note that we make use of the set subtraction operator “\” to exclude nodes 1 and 4 from the set $N$ in the formulation of the second set of constraints.

The complete code listing for solving the shortest path problem on the elytica platform is the following:

model shortest_path
set N = {1,2,3,4}

const d = { {0, 2, infty, 11}, 
            {2, 0, 3, 8}, 
            {6, 3, 0, 4}, 
            {11, 8, 4, 0} }, forall i in N, forall j in N

bin x, forall i in N, forall j in N

min sum_{i in N}{ sum_{j in N setminus {i}}{ d_{i,j}*x_{i,j} }}

constr sum_{j in N setminus {1} }{ x_{1,j} } - sum_{j in N setminus {1} }{ x_{j,1} } = 1
constr sum_{j in N setminus {i} }{ x_{i,j} } - sum_{j in N setminus {i} }{ x_{j,i} } = 0, forall i in N setminus {1,4}
constr sum_{j in N setminus {4} }{ x_{4,j} } - sum_{j in N setminus {4} }{ x_{j,4} } = -1

end


import elytica

def main():
  elytica.init_model("shortest_path")
  elytica.run_model("shortest_path")

  N = elytica.get_model_set("shortest_path", "N")
  print("\n\nShortest path")

  for i in N:
    for j in N:
      val = elytica.get_variable_value("shortest_path", f"x{i},{j}")
      if val > 0.5:
        print(f"x{i},{j}")
  #[print(f"{i} -> {j}") for i in N for j in N if elytica.get_variable_value("shortest_path", f"x{i},{j}") > 0.5] 

    
  return 0

Leave Comment Cancel reply