組合せ最適化ってなんでしょか
組合せ最適化とは、何か1つ、与えられた条件を満たすような組合せなり順番なりを選ぶとき、選べる組合せの中から一番良いものをなるべく短時間で探し出すためにはどうすればいいか、という、その方法を研究する学問です。組合せを選ぶって、何だ、と思う方もいるだろうと思いますので、まずは簡単な例を紹介しましょう。
Ｓさんが、家の不要品を集めてフリーマーケットに持っていき、売ろうと考えています。集まった不要品は以下の通りです。値段もつけてみました。全部を持って行ければいいのですが、会場までは自転車で行かなければいけないので、そんなにたくさんの荷物は持てません。7kgが限界だと S さんは考えています。あと、傘とほうきとラケットは長くて荷物に入れづらいので、どれか1つしか持って行かないことにしました。なるべくたくさんお金が入ったほうがいいので、売値の合計がもっとも大きくなるよう、荷造りをしたいと思っています。さて、どういうふうに荷造りをすればよいでしょうか?
これは、「持っていく不要品の組合せで、もっとも良いものを選ぶ」組合せ最適化問題です。さて、では実際に一番良い荷物の組合せを見つけるにはどうしたらいいでしょうか? 簡単に思いつき、確実な方法は、「すべての組合せを１つ１つチェックして、しらみつぶしに探す」だと思います。この例だと、物が8個ありますから、2の8乗、つまり256通りの組合せを全てチェックすれば、必ず一番良いものが見つかります。しかし、この方法だと、あまりにも工夫がないので、もう少し工夫を入れた方法を見てみましょう。
ビデオに注目して、荷物の組合せを、ビデオを入れるものと、入れないものに分けて考えます。まず、ビデオを入れた組合せの中で、もっとも売値合計が大きいものを見つけます。次に、ビデオを入れない組合せの中でもっとも売値合計が大きいものを見つけます。で、両者を比べて、売値合計が大きいものを見つければいいわけです。
さて、ビデオを入れた組合せの中で、もっとも売値合計が大きいものを見つけるにはどうすればいいでしょうか？同じように、次はラケットに注目して、ラケット（とビデオ）を入れた組合せと、ラケットを入れない（ビデオは入れる）組合せに分けて考えればいいわけです。このように繰り返し分解していけば、一番良い組合せを求めることができます。
この方法、よくよく考えると、実はしらみつぶしに調べているのと同じなんですね。では、なぜわざわざこんなことをしてるのかというと、ときどき、調べる組合せを省くことができるからです。この例では、ラケット（とビデオ）を入れた組合せを調べるとき、すでにラケットとビデオを合わせて 5kg あるので、太鼓を入れると7.5kgで重量オーバーになり、入れられない、ということがわかります。ですので、太鼓はもはや考慮に入れなくて良くなります。さらには、すでにラケットを入れているので、ほうきと傘も入れられず、考慮しなくて良くなります。調べる組合せがだいぶ少なくなるわけです。
こういう、なるべく無駄なチェックをしないで、一番良い組合せを見つけるにはどうすればいいか、速く解ける問題はどんな性質を持っていて、同じ性質を持っている問題はなんなのか、といった研究をするのが、組合せ最適化の研究です。世の中の問題をどうやって組合せ最適化問題に変換するか、企業などで使われる大きな問題を高速に解くにはどうしたらいいか、などの研究も行っています。
例えば、上記のフリーマーケットの問題も、拡張して考えると、倉庫の中に品物があって、そのうちのどれを小売店に出せばいいか、という、プラニングの問題も出てきます。なんとなく、企業活動で出てきそうな問題です。さらに、小売店がいくつかあって、それぞれにどの品物を送るか、とか、いくつか余計に生産できれば、品物を製作料を引いた、売値の総和をもっとも大きくしたい、とか、変化させていけば、いろいろな問題が考えられます。こういった問題の中から、企業活動や、環境調査、研究上などで比較的良く現れるタイプの問題を探し出し、その問題について、研究を進めていくのです。
企業で使われる問題ってどんなのがあるのかな、と思った方は、配送計画、スケジューリング問題、生産計画などの組合せ最適化、あるいは最適化問題を説明したページを見てみてください。
組合せ最適化問題を解くには、普通、莫大な時間がかかります。大きな問題になると、スーパーコンピューターを使っても1年や2年では解けません。ですので、「なるべく最適な解に近い解を見つける」という、いわばある程度いいかげんな最適化を行う、近似解法という方法も研究されています。理論的な保証はないものが多いのですが、経験的に、普通の場合は、誤差がだいたい 5% 程度になると言われています。
たとえいいかがんに見つける、とはいっても、時間をかければ、それだけ精度の良い答えが見つかる可能性が高くなります。ですので、なるべく複雑な計算を、なるべく高速に行うことが、近似解法にとって重要になります。このような計算の高速化には、アルゴリズムの研究が欠かせないのです。