Continuation of the last time

In Previous article, I read the code to find the shortest path from the start point to the end point when I took some points. I couldn't go through all the points in the previous code, so let's think about that part for a moment. Please note that it is a study memo of optimization that has failed in various ways after all. Click here for a variety of textbooks (https://qiita.com/SaitoTsutomu/items/bfbf4c185ed7004b5721).

Implementation details

Last implementation

When I focused on a certain point, I formulated the relationship between the number of roads entering that point and the number of roads exiting that point. At the start point, there is one more road going out from that point, and at the end point, there is one more road going into that point. Other than that, both are the same number. With this implementation, it will not be the shortest path "through all points", so I will try that part.

for nd in g.nodes():
    m += lpSum(x[k] for k, (i, j) in r if i == nd) \
      == lpSum(x[k] for k, (i, j) in r if j == nd) + {source:1, sink:-1}.get(nd, 0) #Constraint

Progress 1: Define the number of lines that go in and out of a certain point

When paying attention to a certain point, if the total number of lines entering and exiting that point is 2 (the end point and start point is 1), it seems that "not passing" will disappear. However, when I actually tried it, it became a pattern that made a ring other than the favorite route. difficult···.

from pulp import *
import networkx as nx
g = nx.fast_gnp_random_graph(10, 0.8, 0)　#When the third argument is 1, the bidirectional route is g.Hold on edges

source, sink = 0, 2 #start point,end point
r = list(enumerate(g.edges()))
m = LpProblem() #Mathematical model
x = [LpVariable('x%d'%k, lowBound=0, upBound=1) for k, (i, j) in r] #variable(Whether to enter the road)
m += lpSum(x) #Objective function
for nd in g.nodes():
    m += lpSum(x[k] for k, (i, j) in r if i == nd) \
         + lpSum(x[k] for k, (i, j) in r if j == nd) == {source:1, sink:1}.get(nd, 2) #Constraint
m.solve()
print([(i, j) for k, (i, j) in r if value(x[k]) ==1])

Here is the result. It should go from 0 to 2, but there is a ring at points other than 0,5,2. How should we connect these two routes?

Progress 2: Introducing the concept of distance on the road

In the previous implementation, we considered all the paths to be the same length and chose the shortest path. In order to make it a little more practical, I tried to see what happens when I put in the concept of length. I once defined the length as "the value obtained by adding the node numbers at both ends of each route". I referred to this article for the manners such as g.edges [i, j] ["dist"].

#https://qiita.com/kzm4269/items/081ff2fdb8a6b0a6112f
n = 10 #Number of nodes
g = nx.random_graphs.fast_gnp_random_graph(n, 0.9, 8)
for i,j in g.edges():
    g.edges[i, j]["dist"] = i+j

The code for the optimization part hasn't changed much, but it's reprinted just in case.

source, sink = 0, 9 #start point,end point
r = list(enumerate(g.edges()))
m = LpProblem() #Mathematical model
x = [LpVariable('x%d'%k, lowBound=0, upBound=1) for k, (i, j) in r] #variable(Whether to enter the road)
m += lpSum(x[k] * g.edges[i,j]["dist"] for k, (i, j) in r) #Objective function
for nd in g.nodes():
    m += lpSum(x[k] for k, (i, j) in r if i == nd) \
        + lpSum(x[k] for k, (i, j) in r if j == nd) == {source:1, sink:1}.get(nd, 2) #Constraint
m.solve()
print([(i, j) for k, (i, j) in r if value(x[k]) ==1])

The one selected for the optimum route is taken out and illustrated. This article was useful for sprint_layout.

def draw(g):
    rn = g.nodes() #Node list
    pos = nx.spring_layout(g, pos={i:(i/4, i%4) for i in rn}) #Node position
    """drawing"""
    nx.draw_networkx_labels(g, pos=pos)
    nx.draw_networkx_nodes(g, node_color='w', pos=pos)
    nx.draw_networkx_edges(g, pos=pos)
    plt.show()

G = nx.DiGraph()
for k,(i,j) in r:
    if value(x[k]) == 1:
        nx.add_path(G, [i, j])
draw(G)

Click here for the drawing result. It seems that this time it happened to be a proper route. The phenomenon of forming a ring should be possible here as well.

Click here for the total distance for the optimal solution. There seems to be this too!

value(m.objective)
>>>81.0

Finally

Optimization fun!