最大マッチング問題を整数計画問題として定式化してpythonで解いてみた

## 事前準備
from pulp import * # pulpをインポート

## 記号の設定
V = [1,2,3,4,5,6,7] # 頂点集合の設定
E = [(1,2),(1,3),(2,3),(2,4),(3,4),(3,5),(3,7),(4,6),(5,6),(5,7),(6,7)] # 辺集合の設定
delta = {1:[(1,2),(1,3)],
         2:[(1,2),(2,3),(2,4)],
         3:[(1,3),(2,3),(3,4),(3,5),(3,7)],
         4:[(2,4),(3,4),(4,6)],
         5:[(3,5),(5,6),(5,7)],
         6:[(4,6),(5,6),(6,7)],
         7:[(3,7),(5,7),(6,7)]} # δ(i)の設定


## 整数計画問題として定式化して解く
prob = pulp.LpProblem(sense = LpMaximize) # 問題を最大化に設定

x = LpVariable.dicts("x",E, cat="Binary") # 変数の設定

prob += lpSum(x[e] for e in E) # 目的関数の設定

for i in V:
    prob += lpSum(x[e] for e in delta[i]) <= 1 # 制約条件の設定

result = prob.solve() # 問題を解く


##　結果の表示
print("解の状態 :",LpStatus[result]) # 解の状態を表示(optimalなら最適解が得られてる)
print("最適値 :",prob.objective.value()) # 最適値の表示
for e in E:
    if x[e].value() == 1:
        print(f"x_{e} =", x[e].value()) # 最適解（値が1の変数）の表示

## 事前準備
from pulp import * # pulpのインポート

!pip install pulp # pulpのインストール 

## 記号の設定
V = [1,2,3,4,5,6,7] # 頂点集合の設定
E = [(1,2),(1,3),(2,3),(2,4),(3,4),(3,5),(3,7),(4,6),(5,6),(5,7),(6,7)] # 辺集合の設定
delta = {1:[(1,2),(1,3)],
         2:[(1,2),(2,3),(2,4)],
         3:[(1,3),(2,3),(3,4),(3,5),(3,7)],
         4:[(2,4),(3,4),(4,6)],
         5:[(3,5),(5,6),(5,7)],
         6:[(4,6),(5,6),(6,7)],
         7:[(3,7),(5,7),(6,7)]} # δ(i)の設定

## 整数計画問題として定式化して解く
prob = pulp.LpProblem(sense = LpMaximize) # 問題を最大化に設定

x = LpVariable.dicts("x",E, cat="Binary") # 変数の設定

prob += lpSum(x[e] for e in E) # 目的関数の設定

for i in V:
    prob += lpSum(x[e] for e in delta[i]) <= 1 # 制約条件の設定

result = prob.solve() # 問題を解く

##　結果の表示
print("解の状態 :",LpStatus[result]) # 解の状態を表示(optimalなら最適解が得られてる)
print("最適値 :",prob.objective.value()) # 最適値の表示
for e in E:
    if x[e].value() == 1:
        print(f"x_{e} =", x[e].value()) # 最適解（値が1の変数）の表示

import networkx as nx # networkxのインポート
import matplotlib.pyplot as plt # matplotlibのインポート
import random # randomのインポート
random.seed(1) # ランダム値の固定

V = [i for i in range(20)] # 頂点集合を設定（頂点数は20）
E = [] # 辺集合の初期設定
delta = {} # δ(i)の初期設定
for i in V:
    delta[i] = []

Pos = {} # 各頂点の座標の初期設定
for i in V:
    Pos[i] = [random.uniform(0,10),random.uniform(0,10)] # 各頂点の座標を[0,10]×[0,10]上の2次元ユークリッド平面上にランダムに配置

# グラフの初期化
G = nx.DiGraph()

# 頂点を追加
for v, pos in Pos.items():
    G.add_node(v, pos=pos)

# 辺を追加
for i in V:
    for j in V:
        if i < j:
            if ((Pos[i][0] - Pos[j][0])**2 + (Pos[i][1] - Pos[j][1])**2)**(1/2) <= 3.5: # 距離が3.5以下の辺だけグラフに追加
                G.add_edge(i, j)
                E.append((i,j))

# δ(i)の設定
for i in V:
    for j in V:
        if (i,j) in E:
            delta[i].append((i,j))
        elif (j,i) in E:
            delta[i].append((j,i))

# グラフの描画
pos = nx.get_node_attributes(G, 'pos') 
nx.draw(G, pos, with_labels=True, node_color='darkorange', node_size=300,font_size = 15, font_color="white", arrows = False, edge_color = "black")
plt.show()

## 整数計画問題として定式化して解く
prob = pulp.LpProblem(sense = LpMaximize) # 問題を最大化に設定

x = LpVariable.dicts("x",E, cat="Binary") # 変数の設定

prob += lpSum(x[e] for e in E) # 目的関数の設定

for i in V:
    prob += lpSum(x[e] for e in delta[i]) <= 1 # 制約条件の設定

result = prob.solve() # 問題を解く


##　結果の表示
print("解の状態 :",LpStatus[result]) # 解の状態を表示(optimalなら最適解が得られてる)
print("最適値 :",prob.objective.value()) # 最適値の表示
for e in E:
    if x[e].value() == 1:
        print(f"x_{e} =", x[e].value()) # 最適解（値が1の変数）の表示

# グラフの初期化
G = nx.DiGraph()

# 頂点を追加
for v, pos in Pos.items():
    G.add_node(v, pos=pos)

# 辺を追加
for i in V:
    for j in V:
        if i < j:
            if ((Pos[i][0] - Pos[j][0])**2 + (Pos[i][1] - Pos[j][1])**2)**(1/2) <= 3.5:
                G.add_edge(i, j)
                E.append((i,j))

# グラフの描画
pos = nx.get_node_attributes(G, 'pos')
nx.draw(G, pos, with_labels=True, node_color='darkorange', node_size=300,font_size = 15, font_color="white", arrows = False, edge_color = "black")
for e in E:
    if x[e].value() == 1:
        nx.draw_networkx_edges(G, pos, edgelist=[e], edge_color='red', arrows = False)


plt.show()