新型コロナの影響で技術書典8は中止になったけど、技術書典 応援祭が絶賛開催中。
そんな中で買ったねず宮ちんじろうさんの『0から分かる！ソート・選択アルゴリズムと資源配分問題』が面白かったので、紹介したい。
概要
アルゴリズムの基本とも言えるソートアルゴリズムの解説から始めて、最終的には資源配分問題を高速に解くアルゴリズムまで説明されている。
図が多く、具体例を使った議論がされてるので、とても分かりやすい。
また、資源配分問題を高速に解くアルゴリズムは、なるほどねという感じ。
資源配分問題、なるほどね。自分だと脳死でMIPにしてソルバーかけちゃいそうだ（＾＾；
— やまいも (@yappy0625) 2020年3月7日
資源配分問題
本書でゴールにしてる資源配分問題というのは、こんな問題：
Aさん、Bさん、Cさん、Dさんは友人から6個のりんごを貰った。
それぞれがりんごをいくつか貰った時の満足度は次の表で表される。
全体での満足度の合計値が最大となるような配分はどうなるだろうか?
人物 0個 1個 2個 3個 4個 5個 6個 A 0 13 24 33 42 48 52 B 0 17 29 37 42 45 46 C 0 16 31 38 41 43 44 D 0 20 38 52 62 67 69
この問題のポイントは、もらったリンゴの個数が増えたときの満足度の上昇が徐々に減っていっていること。
これは経済学で限界効用逓減の法則と呼ばれてる。
そして、それは数学的にみると凹関数といういい性質として捉えることができる。
さっきのツイートの通り、自分だとこの問題は何も考えずにMIP（Mixed Integer Programming, 混合整数計画問題）にして解いちゃいそうだけど、本で紹介されてるアルゴリズムはこの凹性をうまく利用していたので、とても感心した。
アルゴリズムの詳細は本を買ってのお楽しみということでw
MIPでの解法
ここからはオマケで、じゃあMIPだとどう解くのかという説明。
各自のもらうリンゴの数を求めるから、Aさんがもらうリンゴの数を、Bさんのもらうリンゴの数を
、・・・（
は0以上の整数）としてしまいそうだけど、それだとうまくいかない。
こういうときの定石は、Aさんがリンゴを0個もらうかどうかを、Aさんがリンゴを1個もらうかどうかを
、・・・、
Bさんがリンゴを0個もらうかどうかを
、・・・とバイナリ変数で表すようにする。
そうすると、Aさんがもらったリンゴの数はと表せるし、Aさんの満足度も（Aさんが
個もらえたときの満足度を
で表すとして）
と表すことができる。
あとは、Aさんがもらうリンゴの数は0〜6個のどれか1つということに気をつければ、のうち1になるのがちょうど1個という制約が必要と気づくので、次のような最大化問題として書ける：
あとはこれを解くだけ。
GLPKで解いてみる
小さなMIPならフリーのGLPKでも全然解けるので、GLPKで解いてみた。
まず、上記の数式をモデルにすると以下：
# リンゴの数 param AppleCount; # メンバーとリンゴの範囲 set Member; set AppleRange := 0..AppleCount; # 満足度 param Satisfaction{Member,AppleRange}; # メンバーとリンゴの数に対して、配分されるか var Distribution{Member,AppleRange} binary; # 満足度を最大化 maximize TotalSatisfaction: sum{m in Member, i in AppleRange} Satisfaction[m,i] * Distribution[m,i]; # 各メンバーについて、配分はどれか1つ subject to Assignment{m in Member}: sum{i in AppleRange} Distribution[m,i] = 1; # 配分されるリンゴの合計はリンゴの数に等しい subject to CountSum: sum{m in Member, i in AppleRange} i * Distribution[m,i] = AppleCount; # 解いて解を出力 solve; display Distribution; end;
与えるデータは以下：
# 入力データ data; param AppleCount := 6; set Member := A B C D; param Satisfaction: 0 1 2 3 4 5 6 := A 0 13 24 33 42 48 52 B 0 17 29 37 42 45 46 C 0 16 31 38 41 43 44 D 0 20 38 52 62 67 69 ; end;
これをglpsolで実行すると、こうなる：
$ glpsol -m rscprb.mod -d small.dat （省略） INTEGER OPTIMAL SOLUTION FOUND Time used: 0.0 secs Memory used: 0.1 Mb (149031 bytes) Distribution[A,0].val = 1 Distribution[A,1].val = 0 Distribution[A,2].val = 0 Distribution[A,3].val = 0 Distribution[A,4].val = 0 Distribution[A,5].val = 0 Distribution[A,6].val = 0 Distribution[B,0].val = 0 Distribution[B,1].val = 1 Distribution[B,2].val = 0 Distribution[B,3].val = 0 Distribution[B,4].val = 0 Distribution[B,5].val = 0 Distribution[B,6].val = 0 Distribution[C,0].val = 0 Distribution[C,1].val = 0 Distribution[C,2].val = 1 Distribution[C,3].val = 0 Distribution[C,4].val = 0 Distribution[C,5].val = 0 Distribution[C,6].val = 0 Distribution[D,0].val = 0 Distribution[D,1].val = 0 Distribution[D,2].val = 0 Distribution[D,3].val = 1 Distribution[D,4].val = 0 Distribution[D,5].val = 0 Distribution[D,6].val = 0 Model has been successfully processed
見ての通り、一瞬でサクッと解けた。
（Aが0個、Bが1個、Cが2個、Dが3個）
ちなみに、練習問題に載ってた少し大きい問題も以下の通り：
# 入力データ data; param AppleCount := 15; set Member := A B C D E F; param Satisfaction: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 := A 0 36 67 91 109 122 131 135 135 135 135 135 135 135 135 135 B 0 40 78 113 134 149 160 165 165 165 165 165 165 165 165 165 C 0 39 66 83 95 101 105 108 108 108 108 108 108 108 108 108 D 0 26 51 71 90 104 116 126 126 126 126 126 126 126 126 126 E 0 23 36 47 55 62 64 65 65 65 65 65 65 65 65 65 F 0 37 69 97 102 106 109 109 109 109 109 109 109 109 109 109 ; end;
$ glpsol -m rscprb.mod -d large.dat （省略） INTEGER OPTIMAL SOLUTION FOUND Time used: 0.0 secs Memory used: 0.2 Mb (237295 bytes) （省略） Distribution[A,3].val = 1 （省略） Distribution[B,4].val = 1 （省略） Distribution[C,2].val = 1 （省略） Distribution[D,2].val = 1 （省略） Distribution[E,1].val = 1 （省略） Distribution[F,3].val = 1 （省略） Model has been successfully processed
こんなふうに、大きくない問題ならアルゴリズムをまったく考えないでも解けるのがMIPの嬉しいところ（＾ｑ＾）
ちなみに、上記のGLPKの解説は新刊に書いているので、よかったら読んでみてほしい。（宣伝）
もちろん、MIPを使って脳死で解けるのは小さい問題に限るので、紹介した本のような内容も必要になってくる。
なので、紹介した本もぜひとも読んでみてほしい。
今日はここまで！
