[PYTHON] Combinatorial optimization-typical problem-maximum cut problem

Typical problem and execution method

Maximum cut problem

In the undirected graph $ G = (V, E) $, it is assumed that the non-negative weight $ w_ {ij} $ is given to each side $ e_ {ij} = (v_i, v_j) \ in E $. At this time, find $ V_1, V_2 (= V \ setminus V_1) $ that maximizes $ \ sum_ {v_i \ in V_1, v_j \ in V_2} {w_ {ij}} $.

Execution method

usage


Signature: maximum_cut(g, weight='weight')
Docstring:
Maximum cut problem
input
    g:Graph(node:weight)
    weight:Weight attribute character
output
Total cut weights and one vertex number list

python


#CSV data
import pandas as pd, networkx as nx, matplotlib.pyplot as plt
from ortoolpy import graph_from_table, networkx_draw, maximum_cut
tbn = pd.read_csv('data/node0.csv')
tbe = pd.read_csv('data/edge0.csv')
g = graph_from_table(tbn, tbe)[0]
t = maximum_cut(g)
pos = networkx_draw(g, node_color='white')
nx.draw_networkx_nodes(g, pos, nodelist=t[1])
plt.show()
print(t)

result


(27.0, [2, 4, 5])

mct2.png

python


# pandas.DataFrame
from ortoolpy.optimization import MaximumCut
MaximumCut('data/node0.csv','data/edge0.csv')[1]
id x y demand weight
2 2 10 5 0 1
4 4 2 2 1 2
5 5 0 5 1 1

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, 4)
for i, j in g.edges():
    g.adj[i][j]['weight'] = 1
t = maximum_cut(g)
pos = networkx_draw(g, nx.spring_layout(g), node_color='white')
nx.draw_networkx_nodes(g, pos, nodelist=t[1])
plt.show()

mct.png

data

Recommended Posts

Combinatorial optimization-typical problem-maximum cut problem
Combinatorial optimization-typical problem-maximum matching problem
Combinatorial optimization-typical problem-maximum flow problem
Combinatorial optimization-typical problem-knapsack problem
Combinatorial optimization-minimum cut problem
Combinatorial optimization-typical problem-n-dimensional packing problem
Combinatorial optimization-Typical problem-Vertex cover problem
Combinatorial optimization-Typical problem-Stable matching 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-set cover problem
Combinatorial optimization-typical problem-weight matching problem
Combinatorial optimization-Typical problem-Facility placement problem
Combinatorial optimization-typical problem-job shop 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-minimum cost flow problem
Combinatorial optimization-typical problem-Chinese postal delivery problem
Combinatorial optimization-Typical problem-Transportation route (delivery optimization) problem
Combinatorial optimization-Typical problem-Facility placement problem with no capacity constraints
Combinatorial optimization-typical problems and execution methods