リンク

はじめに

今回の記事は、

数理最適化Advent Calendar 2020の23日目の記事です。

qiita.com

今回の記事では、

数理最適化の基本的な問題の一つである、(線形)割当問題の概要と、

www.msi.co.jp

Pythonのライブラリの一つであるscipyを使った解法について紹介したいと思います。

www.scipy.org

(線形)割当問題とは？

(線形)割当問題とは、

ベクトルで与えられた２つの集合A,Bと

それぞれの要素に対するコスト(もしくは得点)を表した行列を元に、

コストが最小化、または得点が最大化されるように、

集合Aの各要素を集合Bの要素にダブリなく割り当てる問題です。

www.msi.co.jp

例えば、5人の水泳選手がいて、

それぞれの選手の、クロール、平泳ぎ、背泳ぎのタイムを

まとめた二次元の表があるときに、

それぞれの競技に誰を一人割り当てれば、

チームの総和のタイムが最小になるか、

を決めることができます。

他の例としては、

複数の部品があり、その部品をいくつかの工場で

それぞれひとつずつ生産するときに、

それぞれの部品を、どの工場で作るようにしたほうが、

コストが最小になるか、などの問題を解くことができます。

この(線形)割当問題を数式で表すと

下記のようになります。

行列C(コスト行列)が与えられたときに、

それぞれの行iを列jに割り当てることをX[i, j] = Trueとする、

真偽値の行列Xを下記の評価式で決定します。

f:id:meison_amsl:20201206135022p:plain

コスト関数の符号を入れ替えることにより、

同じ最小問題を、最大問題として解くこともできます。

scipyを使った解法

実際に線形割当問題を

Pythonのライブラリであるscipyで解いてみたいと思います。

scipyには、この線形割当問題を解くための関数として

scipy.optimize.linear_sum_assignmentが準備されています。

scipy.github.io

この関数を使って、

あるクラス5人の生徒 A, B, C, D, Eの英、国、数の成績のデータがあり、

他のクラスと得点の総和で対決するときに、

3つの教科でそれぞれ一人の生徒を選抜する割当問題を解くコードは

下記の通りです。

from scipy.optimize import linear_sum_assignment
import numpy as np

# あるクラス5人の生徒 A, B, C, D, E(列)の英、国、数の成績(行)を表にした
score = np.array([[4, 1, 3, 3, 4],
                 [2, 0, 5, 2, 1],
                 [3, 2, 2, 0, 5]])
# それぞれの教科で他のクラスと得点の総和で対決するときに、
# 3つの教科でそれぞれ一人の生徒を選抜すると、
row_ind, col_ind = linear_sum_assignment(score, maximize=True)
print(col_ind)
# [0 2 4] = 英:生徒A, 国:生徒C, 数:生徒E が最適
print(score[row_ind, col_ind].sum())
# 14 = 成績の総和

linear_sum_assignmentはデフォルトでは最小化問題を解くので、

最大化問題として解きたい場合は、maximize=Trueとする必要があります。

より大規模な割当問題を解いてみて、

総当り(brute force)の方法との

計算時間の比較をしてみたいと思います。

下記のコードを実行すると、

import itertools
import time
import numpy as np
from scipy.optimize import linear_sum_assignment

score = np.random.rand(5, 10)
start = time.time()
row_ind, col_ind = linear_sum_assignment(score, maximize=True)
max_score = score[row_ind, col_ind].sum()
print(f"calc_time:{time.time() - start:.4f}[sec]")
print(f"{max_score=}")

# brute force
start = time.time()
max_score = 0.0
max_col_ind = None
for v in itertools.permutations(range(score.shape[1]), score.shape[0]):
    sum_score = score[range(len(v)), v].sum()
    if max_score < sum_score:
        max_score = sum_score
        max_col_ind = v
print(f"calc_time:{(time.time() - start):.4f}[sec]")
print(f"{max_score=}")