Shortest vs Longest Path in Weighted Graphs
Alireza Soroudi, PhD
Lead Data Scientist @ bluecrux || SMIEEE || Optimization expert || Healthcare management || Lab Digitalization || Power and Energy systems || Developer || Author / Speaker || (views are mine)
Consider two points on a given graph.
Find the shortest path between these two points.
The MILP formulation is straight forward. The sink-source model can be used for this purpose.
The optimal shortest path is formulated in Pyomo as a MILP problem and solved using cbc solver. The network under study is IEEE 118 bus system. The weight of each edge is defined as the line impedance of each edge.
The result is shown as follows:
Now,
What is the longest path between these two points, without visiting each node more than once?
The previous formulation is no longer valid for this purpose. This means that solving the same problem with maximisation does not work. Why ?
The correct formulation is provided here as follows:
The binary variable S_i is used to find which nodes should be considered in the path (which was not required in shortest path model). The result is as follows:
Some applications of Shortest path are Logistics, supply chain management, planning, transportation and etc.
The applications of longest path are project management, critical path finding and etc.
Subscribe to the?news letter
Some previously published Power System Optimization problems are:
Maps | OS | Cloud | Web | Software
3 年Interested to see how you would add edge reuse to the longest path model? Do it in the data with a multi di-graph duplicating edges? Or In the math?
Retired
3 年Thanks for sharing your work, is beyond my comprehension! But I always like looking at the diagrams. To me they're pictures of what a future power grid might look like. The one above for example, depicts DC Extra High Voltage (larger white line) grid with the underlying AC network portrayed by the lighter colored lines. hmm, How can we decentralized while remaining interconnected?