「重ね合わせ」タイプのモデル応用その三: ポートフォリオ最適化問題

投資すなわちお金を「投ずる」こと、とはよく言ったもので、 例えば株などの資産を購入した途端に自分の手を離れて勝手に価値が上下し出します。 株 A に投資した人がいたとしましょう。株 A はその時点から週単位で 次のような値動きをしたとします。

20週間(約4ヶ月強)買い持ちしての結論は、 価格は 6% 程度の上昇ということになるので 傍目からはそれは良い判断でしたねえ、 ということになりますが、 リアルタイムで値動きを見ている立場に立って見ると気が気ではありません。 この人の気持を理解するため、グラフの書き方を変えて、 現在の価格を前の週の価格で割った「収益率」という指標を表示してみましょう。 前の週に比べて、この株に投じた自分の資産の価値が その時点で 何% 上げ下げしているか、ということを示した棒グラフです。

どうでしょう。例えば最初の 1 ヶ月( 4 週 ) までは前の週に比べて0.2%～0.5% ずつ 下がり続けてます。 6週目から大きくリカバーするので無事帳消しになっていますし、 17 週の下げは 15,16 週と上がった後なのでそんなに心配は要らないのですが、 それは後智恵というもの。その時々には先が見えないので、全く安まりません。 特に巨大なお金をお客様から預って資産を運用する機関投資家といった 立場の方であればなおさらです。

そんなに増えなくてもよいから、 安定的な動きをするように投資したい。 こういう場合に取る戦略が「資産配分(ポートフォリオ)」です。 具体的に述べましょう。 ここに A よりは動きが大人しい別の銘柄 B (買い持ちで 2.7% 程度上昇)があります。

収益率のグラフを描いて、A と並べてみました。

ここで 3 週目とか 11週目とか、A と上げ下げが逆のときがあることにご注目ください。 この二つの銘柄を同時に買って適当に重ねると 上げ下げを消せるような気がしませんか ? 重ね方を按配するには良い方法がありましたね。そうです。 資産配分の問題は「重ね合わせ」のパターンの数理最適化モデルで解くことができまして、 次がそのモデルを図に示したものです。 上げ下げを抑えながらもそれなりに収益を挙げたいので、 ここでは各週平均 0.2% (それでも複利計算だと 1.002 の 20乗 = 1.04 ですから 20週買い持ちで約 4% の収益)を目指すとしましょう。

セット販売の話に例えると、銘柄A あるいは Bを購入したらその上げ下げの履歴（可能性）が 「セット」になって付いてくる。それらを重ね合わせてできるだけ所望の性質の 上げ下げのパターンを得よう、ということです。 「できるだけ平らにしたい」、というのがちょっとこれまでと毛色が変わっていて 若干テクニカルですが(マルコビッツモデルと呼ばれるデファクトスタンダードな方法では、 平らであるということを分散が少ない、という風に表現します)、 ここでは深入りせずに、このモデルがやはり「重ね合わせパターン」の一種であることを 了解頂ければそれで大丈夫です。数理最適化の答を見ましょう。 「銘柄A と 銘柄B を約 60%、40% で分けなさい」というのが出ました。 混ぜ合わせた場合の収益率をAと比較してみたのが次の図です。

赤で示したのが最適な具合に混ぜあわせた場合の収益率です。 上げ下げが銘柄Aよりもなんとなく緩和されているのがわかります (見て取るのは難しいですが制約の効果で、平均の収益率も丁度 0.2% になっています)。 機関投資家の方々は数百から数千の銘柄を一括して相手にして 配分を決定する(ポートフォリオを組む)のですが、 数理最適化なら銘柄の数が大きくなっても「最適な」ポートフォリオを、 ほぼ秒単位で計算することができるので、銘柄数の多いポートフォリオを組む方には必携のツールとなっています。 ただし、お判りのように「最適」ポートフォリオは 銘柄同士の過去の上げ下げの傾向がこれからも続くと考えた場合の話であって、 時系列的な予測をするものでもなく（モデルでは収益の棒グラフの並び順は無視されていますね）、 未来の収益を決して約束するものではありません。 「最適」という言葉は便利なのでついつい使ってしまうのですが、 一定の枠組み(数理最適化モデル)の中だけの話であることはどうかご注意ください。

さて、「まんじゅう」から「ポートフォリオ」まで、若干長い道程でしたが、 重ね合わせタイプのモデルから生成される 数理最適化モデルが多数存在すること、 なんとなく体感頂ければ幸いです。 「重ね合わせタイプのモデル」基本パターンの絵を再掲しますが、 このタイプさえ理解しておけば、ラフな実感ですが 典型的な数理最適化のモデルの大体半分くらいは抑えた、と言えるように思います。

数理最適化モデルの自分なりの分類(重ね合わせ、保存、選択、マス目埋め、対応付け) に解説を加えてみようと軽い気持で始めたこの話題ですが、 いきなり 4 回も使ってしまいました。 次回からは数理最適化モデルのパターンの次のタイプ、 「保存」に進み、よりテンポ良く全体を概括したいと思います。

「重ね合わせ」タイプのモデル応用その二: ネットワーク問題

ネットワークというと何か面倒そうに聞こえますが、 「双六」に沢山の枝分かれが付いたものをイメージすれば大体合っていて、 駒の止まるマスと、マスを継ぐ線からできているひとまとまりを言います。 とある高校の球技大会でのことです。 2年は「バスケ」のあとに「野球」、 3年は「サッカー」のあとに「テニス」が組まれています。 学校としては時間の読めるバスケとサッカーを先にして、 時間の読めない「野球」と「テニス」を後半に持ってくるよう 気を効かせたつもりだったのですが、 不幸にして「バスケ」と「サッカー」の終了時刻が揃ってしまったため 応援の2年全員が体育館から野球場に、 3年がグラウンドからテニスコートに、それぞれ同時に大移動、 渡り廊下(点線)で渋滞を起こして大半が応援に間にあわない、 といった事態になりました。 下にあるのが試合会場の位置関係と廊下の接続具合を示した「双六」もとい、「ネットワーク」の絵です。 2年の「振り出し」/「上がり」は青、3年のは赤で示しました。 数理最適化に現れる「双六」にはこのように「振り出し」と「上がり」が二つ以上現れたりします。

渋滞の理由は 2年、3年が取った標準的な経路(下の絵)を見ると明らかです。 2年、3年の取る経路が途中の廊下で重なっていたためですね。

解消するには次に示すような別の経路に適宜生徒を誘導すればよいはず。

ただ、3年は遠まわりになりますし、こちらはこちらで経路が重なっています。 全員をこのように誘導すると、カーナビのせいで裏道が混んでしまうのと同じで 今度は外回りの経路で渋滞しそうですから、 生徒を「標準の経路」と「別の経路」に配分して誘導する必要がありますが、 さあどうすればよいでしょう？

じつはこの問題、「重ねあわせ」のパターンの一つの典型的な応用になります。 廊下に番号を振ってみました。 例えば 2年の青い経路に人を一人通すと、 その経路を構成する廊下{1,4,8,9} が一人分混む。 3年の同じく真ん中の経路に一人通すと、廊下{3,4,6}が一人分混む。 すなわち「経路」に一人通すと、対応する「廊下」が複数「セット」になって混みます。

生徒は 2年,3年がそれぞれ 100 人ずつ居るとしましょう。 問題の狭い渡り廊下(4番)の容量は 50人分, その他の廊下の容量は 150人分 とします。 容量を超えないように 2年,3年の経路を二つずつ適当に重ね合わせるという 気持を表現すると次の数理最適化モデルになります。 これまで見てきた「重ねあわせ」タイプのモデルと同じ構造をしてますね。

経路が一つしか通ってないので容量超えの心配のないところは 抑え(制約)を入れていません(数理最適化では意味のない制約をこうして 削るのが効率化のコツ)。果たして最適化の答は..? 次のようになりました。 3年の経路を二つに割って、渡り廊下の容量をぎりぎりまで使う (この経路は短かいので推奨されます)。 そして、他は適宜合わせるというものです。

当たり前すぎて面白くない ? 確かに。 この程度ならば人間が瞬時に導くことができます。 しかしこのネットワークの規模が大きくなるとどうでしょう。 考えられる「経路」の数は「○」と「-」の数を大きく上回る勢い (我々の業界の言葉ではこれを「組み合わせ的に」とか言います)で増えて、 「○」が数十個の規模のネットワークでも 人間が場当たり的に最適解を作ることはすぐにできなくなってしまいます。 一方、機械にとっては「経路」(=「詰め合わせのセット」)を列挙して量産することはじつに簡単。 かくして数理最適化は「道路交通網」の渋滞の緩和とか「通信網」におけるルーティングといった 問題に広く応用されるようになっています (実際の渋滞の緩和モデルではもっと精緻に容量の上限と 実際に通っている人の比率で通過速度が決定する、といったモデルになります)。

ネットワークが数千、数万といった規模になって、 経路が無限に近いくらいになったらさすがの数理最適化も困るだろうって? そんな状況にも「列生成法」という解決がちゃんと用意されています。 その話もまた別の機会に。

「重ね合わせ」タイプのモデル 応用その一:生産計画問題

「時間」という概念を入れると「セット販売」のパターンが自然に量産できて 「セット販売」のうまい重ね合わせ、という話がぐっと実務性を帯びてきます。 具体的に申しましょう。今度の例は物を買う話ではなくて作る話になります。 ある製品をある日までに出荷しようとすると、 それに先立って、生産やその準備、箱詰め、といった作業量が「セット」として付随してきます。

次は 4/10 に製品1個を出荷しようとするときに、当日と先立つ 4 日間に 発生する作業量を棒グラフにしたものだとします。

4/10 にできるだけ製品を沢山出荷したいが、各日の作業上限が決まっているとします。 例えば一日50単位の作業しかできないのならば、 このままだと 4/7 の作業量上限がボトルネックになって、下の絵のように 4/10 には 10 個しか出荷できない ?

いえ。沢山作りたいときには、一部作業を前倒ししてピークをカットしますよね。 数理最適化でこの「前倒しによるピークカット」を表現してみましょう。 4/9 以前の作業を「前倒し」するパターンを幾つか作っておきます。 まず一日前倒しするパターン(4/5 から準備を始める)、 さらに二日前倒しして 4/4 から準備を始めるパターンも作っておきましょう。 あとは重ね合わせて作業が所与の値を超えない、ということを表現すれば 数理最適化モデルのできあがりです。

このモデルの数理最適化の最適解は 17個 (標準パターンで 3 個、一日前倒しパターン、二日前倒しパターンでそれぞれ7個ずつ)、でした。 合計作業量のグラフは

という感じで、一日にいろいろな作業を重ねてぎりぎり 50に納めている様子 がわかります。 今度は「作業量」というありがたくないものが「セット販売」になってきていますが、 「重ね合わせて条件を判定」という気持ちは「まんじゅう」のケースと同じ。 モデルに「時間」という要素が入っているので 袋A,袋Bなどの「セット販売」のパターンに相当するものが、 時間をずらすだけで自然に沢山作れてしまいますね。

生産と梱包の作業は違う人が担当するので単純に合計の上限が 50 ではなく、 それぞれ作業上限枠がある、とかパターンの作り方が単細胞すぎるので 質的に違ったパターンを選択肢に入れたい、 といった話もちゃんと取り込むことができて、 ここまで来れば実務的に役立つ生産計画モデルまであと一息、 今時の数理最適化ソルバーなら数千のパターンがあっても解けますので十分実用的です。 重ね合わせタイプのモデルは数理最適化モデルの代表選手で、 違った背景で同じ構造を持つ問題はまだまだあります。 次回は「経路」という概念を入れてネットワーク問題を解く例を紹介しましょう。

「重ね合わせ」タイプのモデル 基本:まんじゅう問題

欲しいものを「それだけ」手に入れるというのは難しいのが普通です。 「この皿だけ」食べたいと思っても定食を頼まなければならないとか、欲しいのは 2,3 曲なのに結局アルバム 2 枚も買う羽目になってしまったとか。とかくままならないのがこの世の中。 そんな「セット販売」しかない状況でも、賢く組みあわせて欲しいものを効率良く手に入れよう。 そういった意図が現れるところに「重ね合わせ」パターンはまず現れます。

一つ典型的な例を挙げましょう。 お客さんが来るので、まんじゅう、もなか、せんべいをそれぞれ 20個/枚 揃えたい。 買い物に行ったお菓子屋さんではこれらが詰め合わせセットになった袋 A,B,C を売っていました。 袋の中身は A にはまんじゅう2個、もなか3個、せんべい5枚、 B にはまんじゅう5個とせんべい2枚、 C にはもなかだけ4つ、 それぞれ入っています。 定価は 500円。B だけはタイムサービスで 500円のところ破格の 100円。 さて、どうやって買い物すればよいでしょう？

上が対応する数理最適化モデルを絵で表現してみたものです (コストを最小に、というのは明らかなので省いてます)。 数理最適化の教科書に出てくるような数式ではないですが、これもモデルの記述の一つ。 数式は数理最適化モデルを表現する便利な道具ですが、 「数理最適化モデルすなわち数式」ではなく、 ユーザーとソルバーが意思疎通する上でベストの手段とは限らないと私は考えています。 このケースではこの絵を例えば Excel とかを使ってインタラクティブに変化するように表すと 制約を体感できます。

最適な答を考えてみましょう。 まずは袋 B の安売りが気になりますね。 なにせ 100円です。10袋買ってまんじゅうとせんべいのニーズを満たして(それでも 1000円)、 もなかを袋 C で調達して、合計 3500円。 ただ、まんじゅう 50 個はちょっと買いすぎですからちょっと無駄が多い気がする。

数理最適化アルゴリズムの回答は、「すべて 3 袋ずつ買って 3300 円」でした。 なるほど。すべて 21 個/枚ずつ、というなかなか無駄のない答です。 まあ人間はもっと賢いので、「せんべい 20枚」という必要量の方を改変し、 8枚で済ませるようにして 2900円(袋B 4 つ、袋C5つ)で済ませてお金を浮かせそうです。 ちょっとモデルをいじってこういう判断をさせるにはどうするかという話もまた面白いのですが、 それは枝葉の話として「重ね合わせ」のモデルパターンの話に戻りましょう。

このモデルのように、「セット販売」のパターンそれぞれの購入量が決定すべき変数になっていて、 パターンを重ね合わせて意図を実現する、という数理最適化モデルの構造を、 私は「重ね合わせ」と称しています。一般化してみたのがこういう絵です。

広い意味での「セット販売」的な状況としてこういうのがあります。 例えば食べ物には栄養素が複数、含まれていますね。 所望の栄養素を所定の量だけ安く摂る、あるいは摂りすぎないようにするにはいろんな食べ物をどういう配分で 食べればよいでしょうか？これは「ダイエット問題」と名前が付いている古典的な例題です。 「摂りすぎない」という上から抑える制約がありますが、構造は「まんじゅう問題」と全く同じです。 他にも天然の「セット販売」と言えば、 重油とか軽油とか様々な成分を含む「原油」がそうで(産地によって値段と含まれる成分が違う)、 古くから石油会社の意思決定に数理最適化が使われてきた理由になっています。 人工的な話だと、時間割が与えられたとして所定の単位数を揃えるためには最低何日学校に行けばよいか、 とか(「曜日」がセット販売のパターン、各日に行われる授業に付属する単位が成分)、 有料 TV の契約をどういう風にすれば、見たい番組がもれなく見られるか、 といった想定が考えられます。

よく数理計画法の教科書の最初に 「部品が3つしかない2種類の製品を生産する計画」とか 「成分が2つの3種類の薬品を混合する計画」とかいう例題が現れるのも同じ流れで、 導入としてこの重ね合わせパターンの例題を採用しているためです。 ただ、ここまで来るとちょっと実務的なケースから程遠く、 逆にこのパターン、本当に役に立つのかすこし不安になってきます。 「原油」は自然が与えてくれた福音とも言うべきすばらしい例題ですが、 「まんじゅう問題」的なわざとらしい状況に出会うことはまずないし、 値段と栄養素だけで食べ物を選ぶのも何です(やってみると卵だけ食べる結果になるらしい、なるほど)。 単位を取るためだけに学校に行くのではないし、 昨今は欲しい番組だけオンライン配信してもらえる。 「セット販売」のうまい重ね合わせができて本当に嬉しいのか？

どうかご安心を。実はこの「セット販売重ね合わせ」の考え方がうまく使えて、 実務的に役に立つケースが多数あるのです。 コツはモデルの設定に「時間」や「経路」という要素を入れること。詳しくは次回以降に。

何て名前だっけ?

「この最適化モデルはどんな方法で解いているのですか?」 先日、お客さまに聞かれました。

ええと普通の LP (線形計画問題) に 0-1 整数変数が入った MILP (線形な混合整数計画法)だから 分枝限定法? でもそれは解法フレームワークの名前に過ぎない。 線形性を利用して緩和問題を解くのは単体法であることも言わなければ、正確じゃない。 でも緩和問題と単体法の説明をしている場合じゃないし..と迷ったあげく、

「標準的な MIP 解法で解いてます。」

と何の情報量もない返答をしてしまいました。「あとは Web で」みたいに、 話し言葉にも適当なリンクが付けられればよいのですが。 もっと言うと昨今の混合整数計画法ソルバーは、 実行可能解を求めるのに各種ヒューリスティック解法まで取り込んでますので 「何々法に基いています」というのがますます難しくなってきています。

最近読んだ本に、病院の診療科は医者側の理屈で分類されたもので ユーザーである患者の立場に立っていない、と分類体系をまるごと見直し、 例えば外科と内科の区別を取り払って成功した話が引かれていましたが、 最適化の世界も全く同じですよね。 ばくっと「凸計画できます!」とか言われて、実務家の方がこれは役に立ちそうだ、と思えるわけはない。 では「生産計画」、「設備計画」、「スケジューリング」、「配車計画」といった名前はどうかというと、 ユーザーの意図の大枠をなぞっただけで絞り込めておらず、今度は解く側サイドが困ってしまいます。

いわゆるソフトウエアの「デザインパターン」と同じ発想なのですが、 問題を持ち込む人、数理最適化モデルを作る人、解く人の間で、ある程度難しさのイメージが共有できる 良い分類や名前はないかなあと、考え始めました。 出してみたのが次です。

• 重ねあわせ
• 保存
• マス目埋め
• 対応付け

他にもあると思いますが、実務で良く現れるのに限って絞りました。 「保存」の代表選手は最小費用流とロットサイジング。 「マス目埋め」はシフトスケジューリング。「対応付け」はレコメンド問題。 ダイエット問題からポートフォリオ最適化問題に至るまで、その他大勢は「重ねあわせ」。 それぞれのタイプに応じて、式ではなくてシンボリックな図や絵を対応付けることができるので、 当事者同士の会話が促進されます（たぶん）。 同じスケジューリング問題でも、シフトスケジューリングは「マス目埋め」だけど、 いわゆるレイバースケジューリングは「重ねあわせ」だからかなり違う、とか 列生成法は大抵の問題を「重ねあわせ」と「対応付け」に帰着してしまう手法だ、とか いわゆる MILP の再定式化で「保存」を「重ね合わせ」に帰着すると、 サイズはでかくなるが、解き易くなる、とか、最適化問題を解く側のノウハウも 蓄積できるのではないかなと思っています。

肝心の「絵」や「図」はどうした？ すみません。続きはまたこのブログで。

最適化モデルの Hello, World

数理最適化の壁は最初の「モデル」を書く部分です。 教科書には「簡単な」モデルが書いてありますが、 なんか現実的ではないのが多いですよね。 部品が 3 つしかない 2 種類の製品を作っている工場の最適化、とか。 こんな高いソフト買って、できるのはそんな程度かね ? と言われては担当者の方も、作り手の我々も立つ瀬がない。

プログラミングの世界には使い手の最初の障壁を取り払うじつにすばらしい発明があります。 それは「Hello, World プログラム」。

// C++ 版
#include <iostream.h>
int main(int argc, char** argv)
{
    cout << "Hello, World\n";
}

端末に Hello, World と打ち出すだけなのですが、 少なくとも自分の指令で CPU を何ミリ秒かだけでも振り向かせることができたのだ、 という満足感があります。

この数理最適化モデル版は何なのかなあと考えて思いたったのがこれ（私がかかわっているソフトウエアのモデリング言語を使っているのはご容赦)。

IntegerVariable x(type=binary),y(type=binary),z(type=binary)；// 0-1 変数
x + y + z == 1; // 品物 x,y,z のうちどれか一つ選ぶ
Objective cost(type=minimize); // コスト最適
cost = 400*x + 500*y + 350*z; // x,y,z はそれぞれ 400円、500円、350円
solve();

答は x = y = 0 で、z = 1。 思った通り「一番安い z (350円) を選びなさい」という結果がすぐに出て、 1つではなくて2つ選ぶときにはどうするのか、 満足度とのトレードオフを取るときにはどうするのか... とか話を広げてゆくことができます。 スモールスタートで問題を成長させてゆくのが 数理最適化モデル作りのプラクティスです。 ソフトウエアが人間との対話的なやりとりの中で人間の考えをどれだけ「引き出せるか」が勝負ですから、 変数を 0-1 (選ぶか選ばないか) にしてあえて「脱色」し 人間側の想像力を刺激するのも手かなと思いました。

余談ですが、ソフトウエア業界のいろんなバックグラウンドの方が この "Hello, World" をどう書くのかという古い ジョークがあります ( 私が好きなのは "Seasoned Hacker" と "Guru Hacker" )。 話のネタにどうぞ。python とかないし、若い方にはどういう意味なのかわからない部分もあると思いますが、 先輩の方にどこが面白いのか聞いてみるのも世代間交流になる? かもしれません。