CodeIQ MAGAZINEで、「プログラマのための数学勉強会」という勉強会のレポートが連載されているのだけど、その第5回で、最適化問題の話が取り上げられていた。
https://codeiq.jp/magazine/2015/07/25428/
自分も大学のときに最適化問題をやっていたので、こうやって最適化問題が取り上げられると、すごく嬉しかったりw
数学というと、初等なもの（計算したり一次方程式を解いたり）はともかく、何やら難しいことをやっているけど、結局何の役に立つのか分からないという場合が多いと思う。
実際には「自然科学を記述するための言語」としてめちゃくちゃ役に立っているのだけど、普通の人はそういったものに触れることもそう多くないし。
数学者の研究のモチベーションとしても、「〜の役に立つから」というタテマエはあるとしても、数学的な対象を研究するという知的な面白さが根っこにはあって、それを追求した結果、たまたま他の問題の解決にも役に立った、というケースが多いと思う。
そんな中、最適化問題は珍しく（？）ダイレクトに数学がどう役立つのかが分かる分野で、実践と理論の中間に位置する数学だと思っている。
なんだけれど、あまり知られていないような・・・
ということで、ちょこっと紹介をしてみたいと思う。
最適化問題とは？
すごく簡単に言うと、「様々な条件がある中で、最善を探す問題」。
こうやって表現すると、どこにでも転がってる身近な問題でしょ？
例えば、様々なタスクがあって、タスク間に依存関係（タスクAをやる前には、タスクBとタスクCを終わらせてないといけない、とか）があるとき、どんな順番でタスクをこなしていけばいいのか、なんていうのも、最適化問題の一つ。
あるいは、人それぞれに好きな食べ物があって、けど、材料には限りがあって、作られる食べ物の数が限られているときに、それぞれの食べ物をどれだけ作ればいいのか、なんていうのも、最適化問題の一つ。
コードの最適化というのも最適化問題の一つで、つまり、プログラムの意味論（メモリがどう変化するのか）は変えずに、コードを出来るだけ速くしたり（速度の最適化）、フットプリントを小さくしたり（スペースの最適化）することを目指している。
少し変わったものとしては、パズルを解くというのも最適化問題の一つだったり。
例えば、「数独」なんかだと、各行、各列、各区画に、1〜9がちょうど1つずつ入るようにする、という条件があって、これを満たすような答えを探すことになる。
（この場合、ちゃんと作られた問題なら答えは1つしかないので、その見つかった答えがそのまま最善という扱いになる）
あと、人工知能の研究なんかでも、最適化問題はよく出てくる。
例えば、紙にある程度のまとまりで赤い点と青い点がポツポツと書いてあって、その赤い点のまとまりと青い点のまとまりの間に境界線を引くことを考えてみる。（パターン分類）
人間だったら、なんとなくの感覚で線を引くことになるけど、機械にこれをやらせようとすると、なかなか難しい・・・
そこで、境界線の一方には赤い点のみが、もう一方には青い点のみがあるようにし、境界線に一番近い赤い点/青い点と境界線までの距離（マージン）を出来るだけ大きくなるように境界線を引かせたりする。
これはSVM（Support Vector Machine）の基本的な考え方で、条件（境界線の一方には赤い点のみが、もう一方には青い点のみがある）を満たす中で、最善（マージンが最大）となる答え（境界線）を探す問題になっているので、最適化問題の一つになっている。
他にも、多数決の「妥当な解決策」について考えてみた。（その1） - いものやま。で取り上げたようなケースもある。
そんな感じで、とにかく何か条件があって、その中で最善が何なのかを探るようなことがあれば、もうそれは最適化問題になる。
最適化問題へのアプローチ
さて、そんな最適化問題だけど、それを考える場合、2つのアプローチがある。
一つはモデル化、もう一つはアルゴリズムだ。
モデル化とは、現実にある最適化問題を、数式に落とし込む作業。
これは、最適化問題の実践の側面と言える。
例えば、条件を数式で書くとどうなるのかを考えたり、あるいは、何が最善であるのかを数式で書くにはどうすればいいのかを考えたりする。
場合によっては、数式じゃなくて、グラフ（点を線でつないだもの）で表現することを考えたりする場合もある。
OR（Operations Research）だと、この研究もけっこう多いイメージ。
例えば、株取引で、確率的に儲けを最大にするにはどうすればいいのか（Stochastic Optimization）や、リスクを出来るだけ抑えて儲けを最大にするにはどうすればいいのか（Robust Optimization）とかがあったはず。
人工知能の研究なんかもそうで、どのように数式に落とし込むのかが肝になる。
もう一つ、アルゴリズムの方は、数式に落とし込まれた問題を、実際にどうやって解くのかという話。
これは、最適化問題の理論の側面と言える。
現実の問題を数式に落とし込むと、そこにはいくつかの代表的なパターンが出てくる。
そこで、あらかじめその代表的なパターンの解法を研究しておくことで、問題を簡単に解けるようにする。
あるいは、その代表的なパターンで出てくる数学的な構造について研究を深めておくなんてことをしたりもする。
ここでよく出てくる代表的なパターンの一つが、線形計画問題（Linear Programming、通称LP）であったり、整数計画問題（Integer Programming、通称IP）であったり。
他にも、二次計画問題（Quadratic Programming、通称QP）や、半正定値計画問題（Semi-Definite Programming、通称SDP）というのがあったりする。
面白いのは、これらは理論的な側面もあるけど、同時に実践的な側面もまだ残っていて、実際にアルゴリズムを動かそうとなるとプログラムを書くことになるので、データ構造をどう作るのかといった問題や計算量の問題、効率的な行列計算を行う方法の問題などが出てきて、そういったこと（計算機科学）を研究している人もいたり。
計算機科学もまた、その奥には理論的な話が転がっていたりで、非常に興味深い。
あと、計算量の話とつながると、「P≠NP予想」というのがある。（未解決問題）
これは簡単に言うと、「どんなにアルゴリズムを工夫しても、計算が簡単に終わらない問題がある（だろう）」という予測。
このような予測があるので、そのような問題に対して厳密な答えを探すんじゃなくて、最悪でも最善な答えのε倍程度に収まる良さげな答えを効率的に見つけるという研究もあったりする。
そのような答えを探すアルゴリズムをε-近似アルゴリズムというんだけど、内容自体はとても理論的なのに、その動機はひどく実践的という、なんとも不思議な話w
そして、そういった研究が先程挙げたLPやSDPの理論的な研究とすごく密接に結びついてたりするから、とても面白いw
ソルバーの話
ところで、CodeIQ MAGAZINEのレポートにあった動画を見ていてちょっと気になったのが、ソルバーの話。
ソルバーというのは数式に落とされた最適化問題を解くためのプログラムで、これを少ない企業が独占している、という話が動画の最後の方でされていた。
実際、ソルバーを売ってる企業は少なくて、しかも高額なので気持ちは分からなくもないのだけど、実際それくらいの価値があるくらいに高速なソルバーを作るのは難しい・・・
例えば、ネットに落ちていたものだけど、Analysis of commercial and free and open source solvers for linear optimization problemsを見てみると、商用のソルバーとフリーなソルバーの性能差は歴然・・・
とはいえ、ちょっとした問題を解くくらいなら、フリーのソルバーでも全然役に立つ。
フリーの代表的なソルバーとしてGLPKというのがあるけど、これでも十分なくらい。
（先程のPDFだと、「GLPKはフリーソルバーの中でも最弱・・・」という結果みたいだけど）
ということで、GLPKの紹介を少ししてみたいと思う。
自己言及パズル
せっかくなので、GLPKで具体的な問題を解いてみたいので、ちょっとしたパズルを。
問題は以下。
次の枠内に 数字がいくつずつあるかを 括弧内に数字で記入しなさい。 +--------------------+ | 0 ( ) 5 ( ) | | 1 ( ) 6 ( ) | | 2 ( ) 7 ( ) | | 3 ( ) 8 ( ) | | 4 ( ) 9 ( ) | +--------------------+
・・・意味、通じるかな？
例えば、これの答えは、次のようになる。
次の枠内に 数字がいくつずつあるかを 括弧内に数字で記入しなさい。 +--------------------+ | 0 ( 1) 5 ( 1) | | 1 (11) 6 ( 1) | | 2 ( 2) 7 ( 1) | | 3 ( 1) 8 ( 1) | | 4 ( 1) 9 ( 1) | +--------------------+
確認してみると、枠内に0は1個、1は11個、2は2個、3は1個、・・・というふうに、それぞれの数字の枠内にある数が、括弧内に数字で書かれていることが分かると思う。
ポイントは、答えとして書いている数字もカウントの対象になるということ。
なので、簡単なようでいて、微妙に難しい。
というのも、答えの数字を変えると、それが他にも影響を与えてしまうから。
例えば、先程の問題で、とりあえず各数字が1個ずつあることから、それぞれの欄に1を書いたとする。
+--------------------+ | 0 ( 1) 5 ( 1) | | 1 ( 1) 6 ( 1) | | 2 ( 1) 7 ( 1) | | 3 ( 1) 8 ( 1) | | 4 ( 1) 9 ( 1) | +--------------------+
そうすると、1が枠内に11個あるので、1が枠内に1個という記述が間違いになる。
そこで、そこを11に変えると、今度は
+--------------------+ | 0 ( 1) 5 ( 1) | | 1 (11) 6 ( 1) | | 2 ( 1) 7 ( 1) | | 3 ( 1) 8 ( 1) | | 4 ( 1) 9 ( 1) | +--------------------+
となり、今つけ加えた1のせいで、1が枠内に12個にw
じゃあ、12に直そうとすると、今度は
+--------------------+ | 0 ( 1) 5 ( 1) | | 1 (12) 6 ( 1) | | 2 ( 1) 7 ( 1) | | 3 ( 1) 8 ( 1) | | 4 ( 1) 9 ( 1) | +--------------------+
となって、今度は枠内の1の数が減って11個に戻ってる、という具合。
（しかも、2の個数も間違ってる）
この様子が自己言及的（「私は今ウソをついています」とか）なので、自分はこのパズルを「自己言及問題」とか「自己言及パズル」と呼んでいる。
このパズルは、枠内に日付や任意の数字列を入れたりすることも出来るので、問題を簡単に作れるというのもいいところ。
次の枠内に 数字がいくつずつあるかを 括弧内に数字で記入しなさい。 +--------------------+ | 2015/07/15 | | 0 ( ) 5 ( ) | | 1 ( ) 6 ( ) | | 2 ( ) 7 ( ) | | 3 ( ) 8 ( ) | | 4 ( ) 9 ( ) | +--------------------+
さて、この問題の答えは・・・？
今日はここまで！
