先日, 0x-seminar - [0x03] 最適輸送の情報科学における進展 というセミナーがあり,最適輸送について熱い2日があったらしいです.私はセミナーの存在を知らず,後からスライドを見ました. 1日目の資料は横井さんの資料で,そもそも最適輸送ってなんなの?とかNLPと絡めてこんな研究あるよ!っと色々とリンクが貼られていて勉強になりました. 2日目の佐藤さんの資料では,直感的な理解を重要視しつつ,最適輸送の問題をきっちりと定式化していて非常に勉強になりました.270ページぐらいあるのですが,すべて見る価値アリです. その中でNetwork Simplexという最適輸送における主問題(輸送量のマトリックスを求める)を解く方法を最初に説明しています.Network Simplex法の解き方を誤解を恐れず簡単に言うと,適当な解から初めて違反的な辺がなくなるまで反復的に修正していく手法です.