マッチング問題を解きたいが, 調べると二部グラフマッチングばかり出てくる.
一般のグラフにおいて, 辺で結ばれた頂点同士をマッチさせたい.
「完全マッチング」「最大マッチング」「極大マッチング」などで調べると, アルゴリズムが出てくるが, 実装するには面倒そう.
速度はそこまで必要ないので, 手軽にマッチングを試してみたい.
そんな人に向けた記事.
マッチング問題
定式化してPuLPで解きます.
高速に解く必要がある人は, 汎用ソルバーではなく, グラフマッチング用の記事を参照しましょう.
問題設定
$n$人がいて, 各人同士で仲の良さが対称行列$W\in\mathbb{R}^{n\times n}$で与えられているとする.
人$i$と人$j$がマッチングするかどうかを$X_{i,j}\in \{0,1\}$で表す.
- なるべく多くのペアを作りたい
- なるべく仲の良い人同士をマッチさせたい
定式化
目的関数
$$
\max_{X\in \{0,1\}^{n\times n}} \sum_{i,j}X_{i,j} + \lambda \sum_{i,j} W_{i,j} X_{i,j}
$$
- 1項目: マッチする数を増やしたい項
- これを制約として$m$ペア以上マッチさせたいとかにしてもよい
- 2項目: 選ばれた辺の重みを最大化したい項
- $\lambda$: バランスを調整する項
制約
- 辺を選ぶか選ばないか
$$
X_{i,j}\in\{0,1\}, \forall i,j
$$ - 各人は別の一人だけとマッチする
$$
\sum_{i} X_{i,j} \le 1, \forall j \\
\sum_{j} X_{i,j} \le 1, \forall i \\
X_{i,i} = 0, \forall i
$$ - Xは対称行列である
$$
X_{i,j}=X_{j,i}, \forall i,j
$$
PuLPを使って解いてみる
定式化した式を書くだけです.
import pulp
import numpy as np
# 人数
n = 10
# 調整係数
lam = 1
# 重み行列
W = np.random.rand(n,n) - 0.5
W += W.T
# 変数
X = np.array(
[
[
pulp.LpVariable(f"X_{i}_{j}", cat="Binary")
for j in range(n)
]
for i in range(n)
]
)
# 最大化問題
problem = pulp.LpProblem("matching", pulp.LpMaximize)
# 目的関数
problem += pulp.lpSum(X) + lam * pulp.lpDot(W, X)
# 制約
for i in range(n):
problem += pulp.lpSum(X[i,:]) <= 1
problem += pulp.lpSum(X[:,i]) <= 1
problem += X[i,i] == 0
for i in range(n):
for j in range(i):
problem += X[i,j] == X[j,i]
# 解く
problem.solve()
# ステータス確認
print(pulp.LpStatus[problem.status])
# 答え
ans = np.array([
[
pulp.value(X[i,j])
for j in range(n)
]
for i in range(n)
])
print(ans)
# マッチした人数
print(np.sum(ans))
# 選ばれた辺
print(np.sum(W*ans))
実行結果:
Optimal
[[0. 0. 0. 1. 0. 0. 0. 0. 0. 0.]
[0. 0. 0. 0. 0. 0. 0. 0. 1. 0.]
[0. 0. 0. 0. 0. 0. 0. 0. 0. 1.]
[1. 0. 0. 0. 0. 0. 0. 0. 0. 0.]
[0. 0. 0. 0. 0. 1. 0. 0. 0. 0.]
[0. 0. 0. 0. 1. 0. 0. 0. 0. 0.]
[0. 0. 0. 0. 0. 0. 0. 1. 0. 0.]
[0. 0. 0. 0. 0. 0. 1. 0. 0. 0.]
[0. 1. 0. 0. 0. 0. 0. 0. 0. 0.]
[0. 0. 1. 0. 0. 0. 0. 0. 0. 0.]]
10.0
4.944025203899315