数理最適化面目を保つ?の巻(ビーズ問題その2)

6000円の予算枠内でできるだけ分量多くビーズを買おうという問題を数理最適化で解いているM君、 「B店からすべて購入」というあんまり面白くない結果になってちょっとがっかり。 まあそれもそのはずで、

店舗	価格/一袋	分量/一袋
A	250円	100個
B	1000円	407個
C	1500円	610個

という設定なので、同じ金額で買えるビーズの数がA店はちょっと少なくB店とC店がかなりいい勝負だが僅差で B店が多い(例えば 3000円で購入できるビーズの数はB店の袋の方が 407×3 - 610×2 = 1 個多い)からでした。

今度はM君、6000円の予算枠をいじるとどういう答が出るか調べはじめました。 えいやと6500円にしてみます。 するとどうでしょう、B店から 5 袋しか買わずに、 わずかながらコストパフォーマンスの悪いC店の袋を 1つ混ぜて購入する、という結果が出ました。 数理最適化はあんなにコストパフォーマンスに敏感だったはずなのになぜか ? それはB店の袋を6.5袋買うという答が許されないので、 B店の袋を 5 つで 5000円分使って残金の1500円で C店から1袋買って お金を無駄なく使おうとしているのです。なるほど。 こういうのを待ってたんだと勢い込んだ M 君、 予算枠をいろいろいじって結果を見てみてみると次のようになりました。

どの店の袋でもコストパフォーマンスがそれほど変わらないので、 可能な限りぴったり予算を使い切ろうとすることに執心している風に見えます。 ただしやっていることは機械なので徹底的。例えば予算 6200 円のときには B店からしか買わずに 200円余す、といういわば「芸のない」回答になっている背後にも「B を 2 つ落として C を使って、残りを A で埋めて..」とかいう組みあわせの検討が実は存在しています。

もし1.3袋の購入とかいう「計り売り」が可能(連続変数の問題)であれば、 常に 6000円分ちょうどを購入できるので最もコストパフォーマンスの良い B 店だけ相手にすればよく、 この問題は非常に簡単です。一方で袋単位でしか買えない(離散変数の問題)となったときには お金が余ってしまう可能性があるため、コストパフォーマンスと同時に予算をいかにすれば使い切れるかという観点で場合分けしつつ具体的に検討しなければならなくなるため問題は圧倒的に難しくなります。 人間には 1袋、2袋 とかいう離散的な世界の方が理解しやすいので、 連続変数の問題よりこちらの方が難しいというのはちょっと直観的ではないところかもしれませんが、 じつは連続変数の問題なら数億変数といったレベルの規模の問題が解けているのに対して、離散変数の問題だと数百変数でも、常に厳密な最適化を出せと言われると場合によってはかなり苦労するというのが実際のところ。そんなわけで離散変数を含んだ数理最適化問題の高速解法というのは世界中で開発競争が繰り広げられている主戦場になっています。

さてさて、問題そのものに没入するのもほどほどにして、 実際的な意味に立ち戻って考えてみましょう。 ここで数理最適化がやっていることは遠足のおやつの買い物で全国の小学生がやっているのと本質的に同じ。

「お金余ったらどうせ取りあげられてしまうんだし、とにかくお菓子に換えてしまわねば。。」

このビーズの件ではどうでしょう。そもそも、より有利にビーズを購入するのが目的だったはずで、 残金を使い切ろうと執着するのは本筋でないのは明らかです。 残金が出たら次の購入機会に回し、やはりコストパフォーマンスの良い B 店の袋を買うというのがじつは正解ですね。問題の世界にどっぷり浸りすぎずに、現実世界に立ち戻って考えてみるのも重要です。

ただ M 君、自分の発見した答への愛着止み難く、6500円を使い切る計画(B店から5袋, C店から1袋)で発注をかけようとしていました。でも後で聞いてみるとその計画はあえなく破綻してしまったそうな。なぜか? いざ注文の段になって気がついたのですが、B店、C店両方に注文すると送料500円が倍かかることがわかったんだとか。残念。