Combinatorial optimization-typical problem-weight matching problem

Typical problem and execution method

Weight matching problem

The weight matching problem is a general term such as "maximum weight matching problem, maximum weight maximum matching problem, maximum weight perfect matching problem, minimum weight maximum matching problem, minimum weight perfect matching problem".

Weight matching problem Problem type Number of matched sides
Maximum weight matching problem Maximize Any
Maximum weight maximum matching problem Maximize Must be equal to the maximum matching problem
Maximum weight perfect matching problem Maximize Must be half the score
Minimum weight maximum matching problem Minimize Must be equal to the maximum matching problem
Minimum weight perfect matching problem Minimize Must be half the score

--All weights are 0 or more. --The minimum weight matching problem is usually not considered because ** empty ** is a trivial optimal solution. --When all the weights are 1 in "Maximum weight matching problem and maximum weight maximum matching problem and minimum weight maximum matching problem", simply "Maximum weight matching problem" Called. --When the weights are all 1 in the "maximum weight perfect matching problem and the minimum weight perfect matching problem", it is simply called the "perfect matching problem". --The minimum weight maximum matching problem and the minimum weight perfect matching problem can be reduced to the maximum weight maximum matching problem and the maximum weight perfect matching problem by changing the weight to "maximum weight-the weight". --The maximum weight perfect matching problem is a solution only when the solution of the maximum weight maximum matching problem is perfect matching. ――From these things, it is only necessary to have a solution for the maximum weight matching problem and the maximum weight maximum matching problem. --The maximum weight matching problem can be solved by the following max_weight_matching (Edmonds method). --Maximum weight To solve the maximum matching problem, specify maxcardinality = True in max_weight_matching below. --If the graph is a bipartite graph, there is an algorithm (such as Hungarian law) that has higher performance than general graphs.

Maximum weight matching problem

For the undirected graph $ G = (V, E) $, when the weight $ w (e) $ of each side $ e \ in E $ is given, $ \ sum_ {e \ in M} {w ( e) Find the matching $ M $ with the largest} $.

Execution method (maximum weight matching problem)

usage


Signature: nx.max_weight_matching(G, maxcardinality=False)
Docstring:
Compute a maximum-weighted matching of G.

A matching is a subset of edges in which no node occurs more than once.
The cardinality of a matching is the number of matched edges.
The weight of a matching is the sum of the weights of its edges.

python


#CSV data
import pandas as pd, networkx as nx, matplotlib.pyplot as plt
from ortoolpy import graph_from_table, networkx_draw
tbn = pd.read_csv('data/node0.csv')
tbe = pd.read_csv('data/edge0.csv')
g = graph_from_table(tbn, tbe)[0]
d = nx.max_weight_matching(g)
pos = networkx_draw(g)
nx.draw_networkx_edges(g, pos, width=3, edgelist=[(i, j) for i, j in d])
plt.show()
print(d)

result


{5: 1, 1: 5, 0: 2, 2: 0, 4: 3, 3: 4}

mwm2.png

python


# pandas.DataFrame
from ortoolpy.optimization import MaxWeightMatching
MaxWeightMatching('data/edge0.csv')
node1 node2 capacity weight
0 0 2 2 4
1 1 5 2 5
2 3 4 2 4

python


#Random number data
import networkx as nx, matplotlib.pyplot as plt
from ortoolpy import networkx_draw
g = nx.random_graphs.fast_gnp_random_graph(10, 0.3, 1)
for i, j in g.edges():
    g.adj[i][j]['weight'] = 1
d = nx.max_weight_matching(g)
pos = networkx_draw(g, nx.spring_layout(g))
nx.draw_networkx_edges(g, pos, width=3, edgelist=[(i, j) for i, j in d])
plt.show()

mwm.png

data

Recommended Posts

Combinatorial optimization-typical problem-weight matching problem
Combinatorial optimization-typical problem-maximum matching problem
Combinatorial optimization-typical problem-knapsack problem
Combinatorial optimization-typical problem-n-dimensional packing problem
Combinatorial optimization-Typical problem-Vertex cover problem
Combinatorial optimization-typical problem-generalized allocation problem
Combinatorial optimization-typical problem-bin packing problem
Combinatorial optimization-Typical problem-Secondary allocation problem
Combinatorial optimization-typical problem-shortest path problem
Combinatorial optimization-typical problem-combinatorial auction problem
Combinatorial optimization-typical problem-maximum flow problem
Combinatorial optimization-typical problem-set cover problem
Combinatorial optimization-Typical problem-Facility placement problem
Combinatorial optimization-typical problem-job shop problem
Combinatorial optimization-typical problem-maximum cut problem
Combinatorial optimization-typical problem-traveling salesman problem
Combinatorial optimization-typical problem-work scheduling problem
Combinatorial optimization-Typical problem-Minimum spanning tree problem
Combinatorial optimization-Typical problem-Maximum stable set problem
Combinatorial optimization-typical problem-minimum cost flow problem
Combinatorial optimization-typical problem-Chinese postal delivery problem
Combinatorial optimization-Typical problem-Transportation route (delivery optimization) problem
Combinatorial optimization-minimum cut problem
Combinatorial optimization-Typical problem-Facility placement problem with no capacity constraints