「ない」ことを示す功罪

厳密に言おうとすると、答えが「ある」ということより「ない」ということの方が難しい。 「ある」ことは答を一個見つけてくればよいのに対して「ない」は網羅的に確認する必要があるから。そういえばあのフェルマーの大定理やリーマン予想もこのタイプの命題です。 ここまで高尚な話を持ちださなくても、なぜ探し物が大変かを考えてみればなんとなく実感できるでしょうか。ちょっと探して見つからなくてもひょっとすると自分の探し方が悪かったのではないかという疑念から根本的に逃れることはできません。要するに「ない」が厳密に言えないので結局探しつづけることになってしまうわけですね。

数理最適化は機械の腕力と数学の力(探し物に電波発振器でも付けるようなことに例えられるでしょうか) を使って、不完全ながらも条件が揃えば「ない」を厳密に示すことができる手法です。 厳密解法と呼ばれるアルゴリズムが「目的関数の最小値は 4 です」と言ったら、 4 よりも小さな答が存在しないことが裏付けとして得られたことになります (けれど、4を与える答は他にもあるかもしれないことはどうか、ご注意くださいませ)。

今年も配信が開始されましたが、CS進出ナンバーを求めるのに数理最適化が使われているのはご存知でしょうか。プロ野球の各チームがクライマックスシリーズ進出(3位以内)を確実にするために何勝すればよいかを求めるところにじつはこの「ない」の積みあげが元になっています。

具体的に説明しましょう。 あるチームの残り試合が 40試合になったとします。 40試合全勝したら少なくとも何位以上の順位が保証されるでしょうか、 まあ、理論的に最良の結果ですから良い順位なのは間違いありません。 ここで 30, 25, 20, .. と勝ち数の仮定を少なくしてゆくと、 最終的に保証できる順位は段々下がってくるはずです。 順位３位以上が保証できればクライマックスシリーズ進出が保証されるわけですが、ここで論理を反転させます。すなわちある勝ち数を仮定したときに4位以下に転落するシナリオが「ない」ことを数理最適化に示させて、クライマックスシリーズ進出の保証を行うのです。 例えば今日 2016/8/11 現在の広島のように19勝を仮定したときにめでたく「ない」が言えるのならば 19勝すれば3位以上に残れることは確実です。そして19が CS進出ナンバーであるかを知るため勝ち数の仮定をさらに減らして「ない」が言えなくなるぎりぎりを探します。さすがに今の広島と言えども 18勝まで減らすと4位以下になるシナリオが存在する。かくして19 がCS進出ナンバーとして出力される、というわけです。

このように数理最適化による「ない」という一見否定的な結論からも厳密な場合には非常に有益な示唆を引き出すことができるのです。が、いつでもそうとは限りません。 例えばマス目埋めタイプのシフト表作りのようなスケジューリングのモデルを作っているとき、 実務的なルールをどんどん取り込んだとして、 すべてのルールを充足する答は果たして存在するものでしょうか。 そんなの一般的にわかるわけない？ ごもっとも。 ただ、私の経験の教えるところによると、ルールが数個を超えたとき、 それらが互いに矛盾しない答があることの方が稀です。 こんなとき数理最適化が答えが「ない」ことを示しても

「数学的に厳密に答がないことを言っているのだな、すごい」

と感心してくれるユーザーは存在しません。 次回はこういった場合にテクニックを駆使して「ない」をいかに「ある」に変えるか、 という話をしてみましょう。