Pave the road with combinatorial optimization

Pave the road in the shortest amount of time

You are an employee of the Civil Engineering Division of the town hall.

--You have to pave the unpaved road network by yourself (because of the lack of manpower). ――Finally, you have to return to the work starting point. ――I want to finish the work as soon as possible.

Way of thinking

Chinese postal delivery problem solves the problem of finding a cycle (a route that goes around and returns) that follows all sides (roads). E5% 9B% BD% E4% BA% BA% E9% 83% B5% E4% BE% BF% E9% 85% 8D% E9% 81% 94% E5% 95% 8F% E9% A1% 8C) I will. It can be calculated in polynomial time using the Floyd-Warshall Floyd method, but here it is a mixed integer optimization problem of combinatorial optimization. I will solve it by catching it. A cycle is known to exist if the degree of all points in the connected graph (the number of edges connected to the points) is even. If the order is odd, you can make a round trip on the same road so that it is even.

The policy is to ask if you should make a round trip on the road. (Since it is relatively easy to find the cycle of a graph with all even-numbered orders, we will omit it here.)

Formulation

(This formulation isn't very good, so a different method is actually better.)

Run in python

Create a random graph.

python3

%matplotlib inline
import networkx as nx
from pulp import *
g = nx.random_graphs.fast_gnp_random_graph(8, 0.3, 11)
pos = nx.spring_layout(g)
nx.draw_networkx_nodes(g, pos=pos, node_size=600, node_color='w')
nx.draw_networkx_edges(g, pos=pos)
nx.draw_networkx_labels(g, pos=pos, font_size=20)
print([i for i, l in enumerate(g.adjacency_list()) if len(l)%2])
>>>
[0, 2, 3, 6]

Since the order of points 0, 2, 3, 6 is odd, we know that we should connect them.

Let's formulate and solve it.

python3

m = LpProblem()
xs, ys = [], []
for i, j in g.edges():
    g.edge[i][j]['x'] = x = LpVariable('x%d_%d'%(i,j), cat=LpBinary)
    xs.append(x)
m += lpSum(xs)
for i, ad in enumerate(g.adjacency_list()):
    y = LpVariable(
'y%d'%i, cat=LpInteger)
    m += lpSum(g.edge[i][j]['x'] for j in ad) + len(ad) == 2 * y
    ys.append(y)
m.solve()
print([g.edges()[i] for i, x in enumerate(xs) if value(x)])
>>>
[(0, 2), (1, 3), (1, 6)]

At the shortest, you can see that points 0, 2, 3, 6 are connected.

that's all