割り当て問題とハンガリー法と整数計画問題と

はじめに

これは、最近興味をもっている（仕事としても色々やることになっている）数理最適化にチャレンジするシリーズの一環です。

今北産業(死語)

忙しい人のために簡単にまとめると

・割り当て問題を勉強がてら実装比較した
・実装はハンガリー法をライブラリを用いて実装、線形計画法
・ハンガリー法はやっぱり桁違いに早いし、厳密解求まるしこれいいね！

ちゃんと作ったら、汎用ソルバーでも早いぞ！ というちゃんとした記事を書いてくださった方が。ありがたい！ 2020/11/18追記
https://qiita.com/SaitoTsutomu/items/b13095b42f7f9e2c7e05#_reference-a3f2f6dcda1bcc057f75

今回対象とする問題

問題としてはポピュラーな「割り当て問題」になります。

解法

ハンガリー法（またはハンガリアン法）という手法があるそうで、それを使用すると高速に、かつ厳密解が求まります。
そのアルゴリズム（手順）をわかりやすく説明してくれているページもありました。

割当問題のハンガリアン法をpythonで実装してみた

性能比較

で、一般的な整数計画法と比較してどれくらい処理時間に差が出るか、比べてみます。
なお、記載していませんが、目的関数の値はハンガリー法、整数計画で同値だったため両方と最適解が求まっています。
※厳密解（最適解）が求まるという情報をご存知の方は教えてください。

まとめ

ハンガリー法は近似解を得るアルゴリズムでなく、最適解が求まる上に非常に高速。
整数計画法でも比較的簡単に実装できるが、速度面では全くかなわないし、実案件ではハンガリー法でよさそうですね。

ソースコード

処理性能測定

from munkres import Munkres
import random
from pulp import LpVariable,LpProblem,PULP_CBC_CMD
from itertools import product
import time

class MyTimer():
    '''
    時刻計測用 のクラス
    '''
    #MY_TIMER = 0
    def __init__(self):
        self.set_timer()

    def set_timer(self):
        self.MY_TIMER = time.time()

    def get_timer(self):
        return(time.time() - self.MY_TIMER)

class assigment_problem():

    def __init__(self,size):
        self.problem    = [[random.randint(1,100) for i in range(size)] for j in range(size)]
        self.size = size

    def solve_hungarian(self):
        my_timer = MyTimer()
        m   = Munkres()
        mat = self.problem.copy()
        self.hungarian_result = m.compute(mat)
        self.hangarian_val = sum([self.problem[val[0]][val[1]] for val in self.hungarian_result])
        self.hangarian_time = my_timer.get_timer()

    def solve_pulp(self):
        my_timer = MyTimer()

        p = LpProblem("AssignmentProblem")
        x = LpVariable.dicts('x',(range(self.size),range(self.size)),lowBound=0,upBound=1,cat='Binary')

        p += sum([self.problem[i][j]*x[i][j] for i,j in product(range(self.size),range(self.size))])

        for i in range(self.size):
            p += sum([x[i][j] for j in range(self.size)]) == 1
            p += sum([x[j][i] for j in range(self.size)]) == 1

        solver = PULP_CBC_CMD(msg=0,threads=8,mip=True,timeLimit=60)
        self.pulp_status = p.solve(solver)
        self.pulp_val = 0
        for i in range(self.size):
            for j in range(self.size):
                if int(x[i][j].value()) == 1:
                    self.pulp_val +=  self.problem[i][j]
        self.pulp_time = my_timer.get_timer()

    def get_result(self):
        return (self.hungarian_result)

    def print_result(self):
        print(f"Hangarian Size {self.size} Value {self.hangarian_val}, time {self.hangarian_time}")
        print(f"Pulp      Size {self.size} Value {self.pulp_val}, time {self.pulp_time}")

if __name__ == "__main__":
    for j in range(10):

        for i in range(10,160,10):
            p1 = assigment_problem(i)
            p1.solve_hungarian()
            p1.solve_pulp()
            p1.print_result()