割当問題に対するハンガリー法と汎用ソルバーの比較

これなに

「割り当て問題とハンガリー法と整数計画問題と」で汎用ソルバーが遅いという記事がありました。
この記事では、コードを少し直して「数理モデルを作成して汎用ソルバーで解く」方が高速であることを紹介します。

Pythonのコード

コードは以下になります。実行にはpip install numpy pulp munkresが必要です。

import random
import time

import numpy as np
from munkres import Munkres
from pulp import PULP_CBC_CMD, LpProblem, LpVariable, lpDot, lpSum, value


class AssigmentProblem:
    def __init__(self, size, seed=0):
        self.size = size
        random.seed(seed)
        rng = range(self.size)
        self.weight = np.array([[random.randint(1, 100) for i in rng] for j in rng])

    def solve_hungarian(self):
        start_tm = time.time()
        m = Munkres()
        result = m.compute(self.weight.tolist())
        val = sum([self.weight[i, j] for i, j in result])
        tm = time.time() - start_tm
        print(f"hungarian {tm = :.2f} {val = }")

    def solve_pulp(self):
        m = LpProblem("AssignmentProblem")
        rng = range(self.size)
        x = np.array(LpVariable.matrix('x', (rng, rng), cat='Binary'))
        m += lpDot(self.weight.flatten(), x.flatten())
        start_tm = time.time()
        for i in rng:
            m += lpSum(x[i]) == 1
            m += lpSum(x[:, i]) == 1
        m.solve(PULP_CBC_CMD(mip=False, msg=False))
        val = value(m.objective)
        tm = time.time() - start_tm
        print(f"pulp      {tm = :.2f} {val = }")


if __name__ == "__main__":
    p1 = AssigmentProblem(300)
    p1.solve_hungarian()
    p1.solve_pulp()

実行結果

※ tm：計算時間（秒）、val：目的関数値
※ 上段がハンガリー法、下段が汎用ソルバー

hungarian tm = 2.43 val = 352
pulp      tm = 1.94 val = 352.0

このように、汎用ソルバーの方が速くなりました。

※ 上記の下段の時間は、数理モデル作成と汎用ソルバー実行の両方を含んでいます。
※ 数理モデル作成はPuLPというモデラーを使い、汎用ソルバー実行はcbcというソルバーを使っています。

参考：最適化におけるPython

主な修正ポイント

• 元の記事で時間がかかっていたのは数理モデルの作成でした。理由はlpSumを使わずにsumを使っていたからです。sumは無駄なメモリを作成し遅くなります。
  • 「数理モデルにおける変数の和」も参考にしてください。
• 数理モデルの変数は0-1のバイナリ変数ですが、連続変数として解いています。割当問題の隣接行列が全ユニモジュラなので、線形緩和しても整数解が得られるからです。
  • 参考：https://www.weblio.jp/content/全ユニモジュラ性

余談

• 今回使用した汎用ソルバーは、cbcという無料ソルバーです。有料ソルバーを使うともっと高速になるでしょう。
• 実務では近似解で十分なことが多いです。近似解法のソルバーを使えば、解の精度とトレードオフですが、さらに高速になるでしょう。
• 今回のデータは完全2部グラフですが、実務ではデータが疎なことが多いです。その場合、変数が減るのでさらに高速になるでしょう。
• NetworkXでも割当問題を解けるのですが、比較にならないほど遅かったです。