A Pyomo Approach to Deal with Graph Related Optimization Problems

What is the shortest path between two given nodes?

How to answer the following questions?

• What are all shortest independent paths between two given nodes?
• What are the all paths between two given nodes?

How complex are these problems?

Here is a sample Graph, Let’s assume the starting and Ending nodes are 1 and 20, respectively.

Image by author

Q1: What is the shortest path between two given nodes?

The answer of this problem is super easy. A linear programming formulation can do the job as follows:

In this formulation :

Wij is the weight of edge connecting node i and node j (parameter)

Gi is a real variable representing the source on node i

Di is a binary parameter representing the existance of demand (sink) on node i. If it is 0 then there is no demand on node i

STi is a binary parameter representing the demand (sink) on node i. If it is 0 then there is no demand on node i

Properties:
The model is LP and is scalable for large graphs (with several nodes and edges.)

It finds the shortest path in one run (there might be more than one solution with the same total length of path)

The Pyomo code for solving the shortest Path problem is as follows:

Image by author

Here is the simulation result:

Image by author

There are 8 nodes in this shortest path [1,3,12,11,1016,17,19,20]

Q2: What are the all shortest independent paths between two given nodes?

Here is the problem formulation:

This is the Pyomo code

Image by author

Here is the results:

Image by author

It is an iterative procedure,

Step 0 : Solve the problem for the shortest path and save the path if there is any

Step 1: Remove the nodes that belong to the previous shourtest path

Step 3: Go to step 0

This model is based on linear programming and can be easily applied to large scale graphs. Some examples are as follows:

Image by author

Q3: What are the all paths between two given nodes?

The concept is very similar to the shortest path. First the shortest path is found and then a CUT is added to the problem and resolved to find the next path. The Idea is to find a new path without repeating the previously found ones. This procedure is repeated until there is no more feasible solution.

DIC={
        for (i,j) in allowed:
            DIC[i,j]=value(instance.U[i,j])
        expr=0
        for (i,j) in DIC:
            if DIC[i,j]==1:
                expr+=1-instance.U[i,j]
            else:
                expr+=instance.U[i,j]
        instance.C4.add( expr >= 1 )}

Initial formulation:

Image by author

By adding these cuts, the algorithm will try to find new solutions with min costs. However, if we just consider the following formulation it will not generate reasonable paths. Let’s give an example: The following answer is a feasible one but you can see the obtained graph is a disconnected one.

Image by author

In order to avoid this situation, we need to add some more constraints to make sure teh graph is connected (after adding the cuts).

(I found more than 2000 different paths ). Some of them are visualized here

Image by author

Si is a binary variable indicating if the node i is in the path.

Here is the Pyomo model:

Image by author

We can also control the length of the paths or the number of allowed nodes in the path:

Image by author

Conclusion:

Shortest path can be easily found with the LP formulation

All independent shortest paths can be found using LP formulation (iterative method), there are usuall few number of them exist

All paths between two given nodes can be found using MILP formulation (iterative method), there are usuall a large number of them exist