「ない」ことを示す功罪

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

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

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

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

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

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

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

最適化で何が実現できるのか(3)

判断材料を増やす

例えばスマートフォンを買うとして、契約プランの決定をする段になったとしましょう。 「利用量が 1G を超えないのならば基本料金お安め従量制のこのプランでしょうかね。 けど沢山使う方でしたらちょっと高いけど定額の契約もこんなにお得です。 ご家族と一緒に契約すると..」とかなんとか。滔々とおっしゃる窓口の方の前で相槌うちながらも内心すごく困っててプランの説明も細かいところはいつしか上の空。 なぜって「自分がどの程度利用しそうか」という最も重要な情報がないのだもの。 プランの説明はいいから「私ってその「沢山使う方」に見えますでしょうか」と聞きたいのが本音ではあります。

会社の業務としてこれと同様の判断を迫られる局面も多々あります。 例えば電力の購入先を変更する、アルバイトさんを新規採用する、大型のボイラーを購入する、 こういった投資を合理的に判断するときどうしても必要になるが得られないことが多いのは、 仮に投資が実行されたときにどういう使われ方をするのか、という情報ではないでしょうか。

実はこの「使われ方」を数理最適化の結果で埋める、という方法があります。 我々は例えば電力契約、プラントの機器、アルバイト人員などの場合を手掛けました。

• 「需要予測を信じると電力プランを切り替えて、従量料金を払った方が得」
• 「大きなボイラーを導入すれば、コジェネを有効に活用できメリットが出る」
• 「ここにアルバイトの人が居てくれれば、社員が本来業務に集中できる」

いずれも業務に組み込んだとき、需要・既存の設備や人員と相互作用して結果が決まることなので、 数理最適化でも使わないとリアルな使われ方予測にならない。 大家さん蓄電池購入のケースはこのごく簡単な具体例になっています。一般に数理最適化は「最適に運用する・運用する」という強力な仮定があるので、 いわゆる「シミュレーション」と比べて外から与える情報が少なく済むのがメリットで、データ不足でも大丈夫。 ただ、あくまで「需要の予測」が正しく「最適に運用できた」という前提があることにはご注意ください。

コミュニケーションを促進する

実務の問題を解く数理最適化プログラムを作ろうとするならばその道のプロにまずは話を聞かせてほしい、とお願いするのが第一歩です。 「特に話すことはないよ」という前置きに続いて繰り出される情報はごく一部で数理最適化案件で言うと「仕様書」のレベルでしょうか。そこから実務家の意識下に埋まっている情報を掘り出す作業を開始するのですが、それには結果を出してダメ出しを受けるのが一番。その過程の中で「そういえば..」「言い忘れてたけど..」として溢れ出てくるこれらの情報は 実務家自身も驚くほど多いものです。 数理最適化の案件で我々が「チューニング」と呼んでいるプロセスはこのためにあります。

こうして実務家のノウハウをある程度(我々の経験値から言うと大体7,8割といったところです) 受け継いだ数理最適化プログラムができあがります。 これをエキスパート自身の居る部署での業務に使うのは普通として、 実は周辺の部署と方のコミュニケーションを促進するためにも使うことができます。 「いつでも聞いてください」と言ってくださる方でも忙しくてなかなか話を聞けなかったり、 あまりに簡単な質問をするのははばかられますが、プログラムならば大丈夫。 （その気になれば）中身だって見られる。 数理最適化プログラムは部署間のコミュニケーション解消の道具として活用するのもあるのです。

さてさて、数理最適化という道具が何ができるのかではなく、 今回あえて「その先」に話題を設定してみました。あくまでユーザーの方々側のお話しなので 我々は道具を提供したゆきがかり上近くに居ただけであくまで「観客」として見聞きしたことがほとんど。 例えば「公正さの追求」「コミュニケーション」といった側面は伺うまで意識したことはありませんでした。 このような事例を見聞きするのは私にとっての素直な喜びであり、 数理最適化の普及に向けての願いでもあります。

最適化で何が実現できるのか(2)

最適化でいろいろやった結果何が実現できているのか、という話の続きです。 どんどん行きましょう。

実行可能性チェックによる安心感

数理最適化という手法のメリットの一つに、出た結果は少なくとも制約式を満たしている、 ということが挙げられます。 実務的に複雑で重要な意思決定であるほど、それを計算機にさせるということには考えも及ばず、 本来は単純作業であるはずの制約式のチェックも含め、まるごと人が請け負うことになっている現場も数多くあります。 そんなときに数理最適化を導入してまず喜んで頂けるのは「最適かどうかはわからないけど、 とにかく実行可能をチェックした結果が出る」というポイントだったりします。

もっともらしい推測

前回から文章ばかりが続いていますので、ここではちょっと例を出しましょう。 次は 8時から18時まで操業している工場を出入りした人数です。

工場から出た人数のうち、青いところがわからないので、 推測するという課題を解いてみます。 負の数や小数以外ならば何を入れてもありな気がしますが、 できるだけもっともらしくしたい。 方法の一つとして隣り合った前後でそんなに人数は急激に変化しないように、 すなわち青い部分が前後の時間帯の平均に近くなるように、 適当に数字を埋める、という手を思いつきました（どうやってやるのか気になる方へ：数理最適化でももちろんできますが、一次方程式を解けばできます）。 結果は次のようになります。

グラフはこんな感じ。

確かになんとなくもっともらしいのですが、この方法には欠点があります。 入った人数の合計が 474人なのに、 出ている人数の合計が 518人でつじつまが合っていません。 差の 44人を解消するにはどうすればよいでしょう。いくら推測とはいえ恣意的に手でいじるのは気が引ける。 こういう場合、数理最適化がもっと良い方法を提供します。 それは数字が従う事実を「制約」として組み込んでしまうのです。 この場合では工場のオープンとクローズ時の人数はゼロで、 工場に入った人は必ず出てゆき、消滅したり増えたりしない(「保存」)。 もっと細かく言うと例えば15時台に入った人はそれ以降の時刻に出てゆく、 時間を遡って13時台に出ることはありません。 細かくなるので述べませんが、この制約は 「保存」タイプ の数理最適化です。 この制約を満たしながら、人数が前後の時刻の平均に近いようにした結果が次（推測２）です。

どうでしょう。確かに合計がちゃんと揃っています。 グラフで比較してみましょう。

データが不足している状況でスタンダードな回帰など普通の統計的予測モデルを作ろうとしているとき、あまりに自由度が高く汎化性能の低いモデルができてしまう場合があります。 そんなときに有効なのが、例えば回帰だったら回帰係数に制約を入れるなど「モデルに構造を入れる」方法です。この例では人数の保存を表現する制約を入れたわけです。 数理最適化は追加する制約の自由度がかなり高く、このアプローチには有用な解析手法です。 得られる情報が増えると、予測の確からしさを増やすことができることもこのアプローチのメリットです。例えばこの工場のケースでは「工場における一人の平均滞在時間」が手に入ったと考えると、制約はもっと詳細化できて予測はより精緻になりますね。

また次回。この話題をもうすこし続けます。

最適化で何が実現できるのか(1)

最適化で「何をしているのか」と問われれば、 「運転計画」「スケジューリング」「配送計画」「ポートフォリオ最適化」 といった月並な答になってしまいますが、 ここでは数理最適化にこれらをさせることによって、 結局「何を実現しようとしているのか」という 「動機付け」そのものについて私の経験から拾ってお話してみたいと思います。

コストの削減

品質の要件を満たす製品をできるだけ少ない材料コストで作りましょう、 経路の長さ(輸送の費用)最小で所定の場所を巡回するルートを探しましょう、 在庫にある原材料を使ってできるだけ高く売れて利益の出る製品を作りましょう、 といった具合に数理最適化の教科書の例題はコスト削減や利益最大化を意図したものがじつに沢山あります。 また、単純な例題の結果もビーズの例のように、わずかでも得となると、購入先をすべて乗りかえてしまうといった単細胞なものなので、 最適化を冷徹なコストカッター、利益追求を極限まで突きつめるための技法、 と思われている方も多いと思います。

実際には、「コスト削減」だけを旨とした最適化はむしろ少数派なのです。 ただ、重宝されているのは確かで、 代表選手としてはネット広告配信(費用対コンバージョンの調整)があります。 設定が人工的で結果の評価軸が「コスト」「コンバージョン」の二つ、 という具合に少ないので数理最適化がうまくはまると言えるでしょうか。 また人間が介在することができないくらい大量の意思決定が必要、という特性も適用を後押ししています。 数理最適化がエネルギーの分野で適用例が多いのも、 この分野では「コスト」という尺度がかなり重要視されるところから来ていて、 プラントの運転最適化(需要予測に基いてプラントの機器の運転を決定する)という代表例があります。 ただ、この分野も「環境負荷軽減」という、 ときに「コスト」に対して真っ向から相反する尺度が入っていますので、 数理最適化一発で結果を求めるという風にならないことも多くなっています。

公正さの追求

人の割り当てといった業務は、人間の熟練者にはまずかないません。 夜勤の後に休暇を取るとか、月あたりの勤務時間の制約を守る、 とかいうのは満たせてあたりまえの話であって、大事なのはその先です。 休暇の間隔をなるべく同じにする、つらい業務を一部の人に偏らせない、 担当できる職務が一緒ならば担当回数が揃うようにする、 残業時間は賃金に直結するのでなるべく差をつけない、 など「平等であること」の追求は「働きやすい」職場の実現のために欠かせません。 一方で各人の立場に応じた割り当ても必要です。 例えば店長さんは掃除や棚出しなど、店の業務は何でもできますが、 通常はレジを担当していて棚出しするのは人繰りが逼迫しているのが自然ですね。 熟練者のスケジューリングは相反した要求が緊密なバランスの下に成りたっていて、 「アート」の領域だと言ってよいでしょう。

ただ、人間のやることなのでスケジュールを作成する人の癖による偏りは消せません。 そんなつもりがなくても、なぜ「俺は月曜に夜勤が多いんだろう」 「なぜ私の勤務希望は通りにくいのかなあ」とかいう疑問が職場の雰囲気に影響します。 機械が独立な立場で行うことで「公正さ」が実現する。 数理最適化が自動でスケジューリングを行う意図の一つはここにあります。

ただ、数理最適化は人間の「アート」を実装するためにかなりの苦労を強いられます。 この手のモデルはマス目埋めタイプを骨組としていますが、 平等性や自然さを実現するために、 他のメンバーがどのような勤務をしているかにも関連させたタイプの制約を多数入れる必要があります。 我々はお客様とのやり取りを通じて平等性や自然さの表現方法のコツを学びました。

熟練者のサポート

社会的にも大きなインパクトのある、お金にすると数億円以上といった 大規模な意思決定を毎日、業務として行いつづけている方がいらっしゃいます。 いつも驚くのはそのような決定を行っているのは、大人数のチームではなく、 かなり少数の熟練者の方々だということです。

実務的な最適化を業務としていて、 そういった方々とお話する機会が得られるのは私にとって最も嬉しいことの一つですが、 話を伺っていつも思うのは、彼らの頭の中には定式化されていないにせよ、 問題とその解き方が整理されているので、 数理最適化はまずそれらをトレースすることを旨とすべし、ということです。

解き方なんか聞かなくても問題の条件だけから数理最適化によってもっと「最適な」答が出る? それこそあまりにおこがましく、非科学的な態度というものでしょう。 数理最適化が考慮できるのはモデル化された数式の範囲だけ。 モデル化された定式もいつも 100% 解けるとは限らないのですから。 重要な意思決定に数理最適化が貢献できるとしたら、 ノウハウを数理モデルの形で明確化し、人手を煩わせないで結果を出すことができる、 という点においてです。 工夫次第で数理最適化は、熟練の実務者の7,8割程度の答なら出すことができます。 この答をリファレンスに使って後継者を育てる、とか 平常業務は機械に任せて、熟練者は人間ならではの難しい判断を要求されるイレギュラーなケースに対応する。 また、常に忙しい熟練者を煩わせないよう、 簡単な問いあわせならば数理最適化に答えさせるようにする、といった役割分担ができます。

３つ紹介しましたがいかがでしょうか、数理最適化にさせていることは多種多様でも、 「動機付け」については意外と共通している部分も多いのではないかとも考えます。 もうすこしあるのでこのトピックで続けてみましょう。

あれもこれも良くしたいのだけど..(2:重み調整に頼らない方法)

前回は数理最適化を使って、利便性と安全性を共に追求する地点を探そうとして目的関数を

(利便性重み)×(地点の利便性) + (安全性重み)×(地点の安全性)

という「重み付き平均」にしたは良いのですが、 候補になる土地の形が直線的なときにちゃんと「按分」された結果が出ないという話でした。

重みの按分は上の図の青い点線の傾きに反映していて、 傾きが緩ければ A 地点が最適解(左の図)、きつければ B 地点が最適解(一番右の図)。 問題は利便性重みと安全性重みが同じ（真ん中の図）ケースで、 A 地点、B 地点とその中間地点がすべて「最適解」となってユーザーを襲います。

プログラム開発作法の文脈での数の数え方は「1 つ、2 つ、沢山」。未開の民族の言語みたいですが、要するに 3つ以上あるならば汎用化を意識しろという意味です。 実務的な数理最適化における最適解の数は「まれに 1 つ、普通は沢山、じつは無限個」。 「最適(最も良いもの)」という言葉の印象から我々は無意識に「最適解」は唯一だと思っているフシがありますが、この例に見るように最適解が一つに定まらないケースが結構あって、 最も基本的かつ強力な数理最適化である線形計画法でも出現してしまうのです。 上で無数の最適解が「襲う」と言いましたが、 同等の無数の解がある、ということがユーザーに「見える」わけではなくて、数理最適化ソルバーの都合で無数の最適解があってもそのうちのどれか一個が出てくるだけ。 さて、そんなときにユーザーとの対話を通じて無数の最適解候補を具体的に出力させる常套手段を紹介しましょう。

適当に軸になる目的関数の尺度(仮に安全性)を決め、 まず安全性だけで最適化、結果として得られる A 地点が持つ安全性の値("1" とします)をどこまで折り合えるか(例えば 0.8 とします)を考え、

安全性が 0.8 を下回らない中で、可能な限り利便性を最大化する

という問題を解きます。そうすると、結果として許される領域は小さくなって、 安全性が 0.8 を下回らない範囲で利便性を最大化した「地点 C」が最適解として出ます。

あとは同様で、この "0.8" という値を変化させてこれを繰り返せば、 最適解のバリエーションが一つずつ出力されてゆきます。

線形計画問題の答が按分された答になってくれないのは「シーソー」がわずかな重さの差でも必ずどちらがが上がり切ってしまうことに似ています。目的関数の重みは両側に載せる重しのようなものなのでここをいかに按分調整しても（完全に釣り合わせることができない限り）結果は二通りしか出てきません。

ここで紹介した、制約を追加して探りを入れる、 という方法はシーソーの片側を手で抑えて、力を加減することに相当します。 こうすればシーソーを自然に任せた場合とは本質的に違う結果を見ることができる、というわけです。少々面倒ですがいろいろな状況で使うことができる汎用性が高い方法ですから、二つ以上の目的関数があるとき、重み調整の代替手段としてぜひご検討ください。

あれもこれも良くしたいのだけど..(1:「重み係数」の怪)

エネルギー最適化における、CO2排出量とエネルギーコスト。 積み付けにおける、作業効率とスペース効率。 はたまた生産計画問題における在庫切れリスクと商品廃棄コスト、 そうかと思うとポートフォリオのリスクとリターン、といった具合に 実務的な数理最適化モデルは「あちらが立てばこちらが立たず」という状況(トレードオフ)だらけで、「あなたの満たしたい要件はこうすればすべて OK 」という結果が出ることはほぼありえない、と言って良い状況です。

我々:    「こういう結果になりました」
お客さま:「おおっ、これは思いもよらなかったよ、すばらしい!」

とかいう絵に描いたような展開になることはそうそうなくて、

我々:    「こういう結果になりました」
お客さま:「やっぱ、そうだよねえ。。うーん。」

という感じが普通です。 まあすべて良くなる方向が見えているのならば、 別に我々に頼んで最適化するまでもない、ということかもしれませんね。

今回はトレードオフのあるケースにおける定式のテクニックについて述べます。「そんなん簡単。適当に重み付けして目的関数を足し算すればよいんじゃないの？」というのが通り相場です。然り。我々専門家もこういう定式化を自ら提案したりします。ただ、注意は必要で、結果は必ずしも「重み」に従ってくれない場合もあるよという、ちょっと怖い話をしましょう。 例で説明します。次のような形の工場用地を持っている会社があったとして、 倉庫をどこに建てるかを決めたい、とします。

工場は右の方にあるので、倉庫は右に建てるほど利便性は高い。 ただ、図の下は海岸に近くて津波とかが心配。 将来のことも考えると図の上の方に建てる方が安全です。 そんなわけで可能な限り安全で利便性の高い場所を適当な折り合いで決定したい。 こんなとき数理最適化の目的関数は、例によって重み付き足し算になります。

目的関数（最大化）： (利便性重み)×(地点の利便性) + (安全性重み)×(地点の安全性)

出てくる答は大体予想が付きます。 安全性最高のA地点と、利便性最高のB地点の間、黄色い境界線上のどこかですよね。 なぜなら C 地点のような場所は中途半端で同じ利便性でより安全な場所、 あるいは同じ安全性でより利便性の高い場所が存在するので最適解にはなり得ない。 利便性/安全性どちらかの意味で「最適性」をつきつめて行くと境界になってしまうわけです。

さて、百聞は一見に如かず。利便性と安全性の重みが足して 1 になるように 振ってみて、数理最適化によって導かれる場所がどうなるか見てみましょう (数式表現が気になる方へ、用地の境界は円弧で、x 座標、y 座標で地点を現わすとします。 4分の1円を実行可能領域として適当な線形関数を最大化します)。

利便性の重みが 0 の場合には最も安全な A 地点が選択され、 利便性の重みが増えるにつれて、境界上を最適地点が動いてゆき B 地点に至っています。 全くもって期待通りで、面白みがない結果ですが、 じつはこれ、重みの設定に従って結果がちゃんと動いてくれる、 かなり幸運なケースなのです。

ここで、次のように用地の形が三角形の場合について同じ問題を解いてみます。

最適な場所の所在についての考察は丸い場合と全く一緒。 やはり境界上にいろんな度合いで按分した答があります。 同じ目的関数でやってみましょう。どういう結果になるでしょうか。

どうでしょう。 まとめて眺めると、安全性の重みがちょっとでも大きければ A 地点、 利便性の重みがちょっとでも大きければ B 地点、ということなのだなとわかりますが、 重みを触っている当事者になってみるとこの応答は「不気味」の一言。 ちょっとつついても全く反応がない。と思ったら、 「ばしゃ!」とばかりいきなり跳ねる、魚みたいです。じつは ビーズをどっちの店で買ったらよいか問題 で起きていたのも同じ現象でした。

これはいったいどうしたわけなのか？ 実はこの問題、数理最適化ソルバーを持ち出さずとも結果の見当は付きます。 図をそのまま、x-y 平面だとしますと、 この場合の最適化とは三角形の領域内の点で、 その点を通る、ある直線のy軸の交点(y切片) を最大にするものを見つけることに相当しています。 その「直線」は目的関数(の等高線の一つ)になっていて、 傾きは安全性と利便性の重みの相対的な大きさから決まります。 安全性の重みが大きければ傾きは緩いので A 地点(左の図)、 利便性の重みが大きければ傾きはきついので、B 地点(右の図)がそれぞれ答になります。

安全性と利便性の傾きが丁度同じ場合には、 境界のどの点を取っても目的関数は同じになるので、 じつは答は一つに定まりません。言ってみれば境界上が全部答で、上の表では代表として、中点が出ているだけです。 こういうときにどれを出すかは数理最適化アルゴリズムの個性が出るところで、 「民主的に」中点を出すのは私がこの問題を解くのに用いた「内点法」という数理最適化アルゴリズムの特徴です。

ここでは重みつき按分で目的関数を設定しても出てくるのは A 地点とか B 地点という極端な結果の「二択」になってしまう例をご紹介しました。問題の構造に依りますが、一般に按分重みに対して結果は滑らかに反応するとは限らず、バランスの取れた解が出てこない場合もあること、どうかご注意ください。 この場合には結果のありかを目で「見る」ことができたのでそうと気づくことができましたが、 実務的な応用だと規模が大きくて複雑ですからどういう答が出るかというのはわからないのが普通です。極端な解が出てきていることにすら気づかないという危険だってあります。

次回は「重み按分」よりも、確実に多様な解を出す方法をご紹介しましょう。

数理最適化面目を保つ?の巻(ビーズ問題その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円が倍かかることがわかったんだとか。残念。