輸送問題を近似的に行列計算で解く（機械学習への応用つき） - 私と理論

輸送問題と呼ばれる問題があります． この問題は，普通は線形計画法やフローのアルゴリズムを使って解かれます． この記事では，この輸送問題を近似的に行列計算で解くアルゴリズム（エントロピー正則化 + Sinkhorn-Knopp アルゴリズム）を紹介します． 輸送問題とは アルゴリズム 得られる解の例 なぜこれで解けるのか？ 競プロの問題を解いてみる 機械学習界隈における流行 まとめ 輸送問題とは 輸送問題とは以下のような問題です． 件の工場と 件の店舗からなる，ある商品の流通圏があるとする． 各工場には 個の在庫がある.． 各店舗では 個の需要がある． 在庫の総和と需要の総和は等しいとする （すなわち ）． 工場 から店舗 に商品を一つ運ぶためには の輸送コストがかかる． 各工場 から各店舗 への輸送量 を適切に決めて，各店舗の需要を満たしつつ輸送コストの総和を最小化せよ． 輸送問題は最適化

[tagomoris]

へぇ、こんな方法あるのか。というか実際の流通とかの現場では既に使われてそうな気もするな、厳密な最適解とかほとんどの場合は要らないし。

[herikutu]

こういうの応用できるとかっこいいな

[ytel]

アルゴリズム解説や読みものとして面白かったのでメモ。

[call_me_nots]

“20行くらいで実装できそうです．なんとこのシンプルなアルゴリズムがかなり良い解を出力してくれる”

[xjack]

組合せ最適化のいい資料が見つかった，と思ったら2013年のものだった．ここに書かれてるソルバーの事情は変化してるんだろうか？ https://www.slideshare.net/shunjiumetani/ss-17197023

[misshiki]

“ややこしそうな最適化問題がこんな単純な行列計算で（近似的に）解けるのはけっこーびっくりですね．”

[yarumato]

“輸送問題（各工場から各店舗への輸送量を適切に決めて輸送コストの総和を最小化）は現実世界での応用が多く，最大マッチングや最小重みマッチングを特殊ケースとして含む重要な最適化問題です．競プロの問題”

[rryu]

「確率分布間の距離」を「確率分布aから確率分布bに確率を輸送する際の最小コスト」ということにすれば輸送問題の近似値算出のアルゴリズムが使えるという話。

[knok]

EMD/WD周りの話も関係あるのかな

[okidate]

　絶対に読まないけど、、、輸送問題はいつか仕事の課題になるのでめも...