「離散最適化の数理：劣モジュラ構造のおもしろさ」　京都大数理解析研究所　藤重悟教授

　最近、最適化という言葉がよく使われる。最適化の手法は工学的な諸問題はもちろん、経済、経営、環境、情報などに関わる様々な問題解決に使われ、産業活動の効率化や人類福祉の向上に役立っている。

　ここで話す最適化とは、「オペレーションズ・リサーチ（ＯＲ）」という分野の学問である。ＯＲのうまい日本語訳はないが、「やりくり学」とでも呼ぶのが適当だろう。「計画、設計、運用、経営、管理」の科学と考えればよい。ＯＲは第２次世界大戦中に英国において、ドイツ軍の攻撃から国を守るために研究が始まり、米国に渡って進展した。軍事研究という不幸な生まれ方をしたが、戦後は産業活動の効率化に大きく寄与し、現在も活発に研究が続けられている。

　ＯＲは、例えばｉＰＳ細胞を発見するような、新しいものを見つける学問ではなく、現実に利用可能なものを最適に運用し、目的を達成しようとする科学である。東日本大震災の時の避難や救援では、ＯＲがもっと活躍すべき状況はあったが、想像をはるかに超える大規模な災害で、十分にはうまく機能しなかったように思われる。

◆効率の良い解法が構築できる「劣モジュラ構造」

　「離散最適化」は、有限な数の物事の、有効な組み合わせ方を導く手法だ。最短経路（カーナビ）、配送計画、人員配置、物流、交通・通信のネットワーク設計、避難誘導を見つけることなど、多くの問題を解決するために用いられている。

　離散最適化の問題では通常、解の個数が有限である。したがって、最適な解はすべての解を調べれば見つけられるという意味で、数学的には簡単な問題である。しかし、この有限な個数が莫大であり、実際に使える離散最適化の技法を構築するためには、知恵と工夫を必要とする。

　例えば、Ｎ個の物があって、このすべての組合せを調べなければならないとすると、その数は２のＮ乗になる。もしＮが１００ならば、最適なものを探すためにすべての組み合わせを調べようとすれば、１秒間に１００万個の組合せを調べられるコンピューターを使っても約３００万年かかる。

　ところが、問題の有効な数学的構造を見つけて、Ｎの３乗個の組合せを調べて最適解を見出せるとすると、同じコンピューターを使って約１秒で済んでしまう。そこで、Ｎのｋ乗という、ｋの値が小さくなるような上手なアルゴリズム（解法）を作る努力がなされる。このようなうまい解法が作れるような離散的な構造として「劣モジュラ構造」がある。その構造を利用すると、うまくいく例では、計算する組合せを２のＮ乗から、Ｎの２乗くらいには落とせる。

　あるシステムの構成要素の集まりを考えて、その一部分の集まり（グループ）ごとに、（費用などに対応する）指標が与えられているとする。重なりのない二つのグループが、別々なグループとして持つ二つの指標を合わせた値が、それらを一つのグループにまとめるとより小さい指標になるというような性質を、少し一般化したものが「劣モジュラ構造」である。劣モジュラ構造は、効率的な解法の構築を可能にする。

◆複雑なシステムの最適化に貢献

　例えば、１６軒の家が繋がるように、なるべく少ない費用で通信線を引く問題を考えてみよう。

　下図のように１６軒の家（黒丸の点）を結ぶ工事可能な３３のリンク（線）の候補があるとする。少ない費用で通信線路を構成するには、すべての家が繋がり、無駄な線はつながないようにするとよい。そのような構造は、閉路（ある点から引かれた線がぐるっと回って元の点に戻る構造）のない木の枝のような構造となる。

　なお、各線には重み（点数）が付けられているが、以下では重みの総和が最大となる通信線路構築の問題を考えるので、重みは費用の裏返しの効率を表していると考えるとよい。この問題は、最大重みのつなぎ方を見つける問題となるが、次のように単純な解法によって解くことができる。

　（１）８、７と大きな重みの候補（線）から順に選んでい　く。

　（２）６の重みの場合、すべて選ぶと右下に閉路（正方形）が　できるため、それを避けるようになるべく多くの線を選ぶ。

　（３）５以下の重みの線についても同様にする。

　（４）３は１つ線を選べば、それ以上は閉路ができてつなげない。２以下も同様。全部の家がつながり終了。

　このようにして得られた線の重みを足した数は８２になる。

これが最適な通信線の引き方であることが、この問題が持つ劣モジュラ構造によって、理論的に保証される。「これが最適解である」と言い切れることが、離散最適化の理論の真骨頂である。

　この解き方は、重みが大きい順に閉路ができないように線を選んでいくと最適解が見つかる「貪欲アルゴリズム」という手法である。また、貪欲アルゴリズムが正しく最適解を見つけることは、その問題が劣モジュラ構造を持つことと同じことである。このような劣モジュラ構造は、多くの物や人がかかわる複雑なシステムの最適化にしばしば役立っている。

　□ふじしげ・さとる□１９７５年京都大大学院博士課程工学研究科修了。東京大助手、筑波大教授、大阪大教授などを経て、２００３年京大数理解析研究所教授、０９〜１１年同所長。専門は離散最適化。

　※例題の詳細は藤重教授のホームページにあります。

　http://www.kurims.kyoto-u.ac.jp/~fujishig/shinagawa2012-03-02.pdf