あれもこれも良くしたいのだけど..(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円が倍かかることがわかったんだとか。残念。

「厳密さ」は人を惑わす(ビーズ問題その1)

ここは手作りアクセサリーの店。 ビーズの残りがなくなってきました。良く使うタイプなので多めに、予算 6000 円で調達します。 調達先の候補をネットショップでざっと探してみると次のような感じです。

店舗	価格(一袋あたり）	分量
A	250円	100個
B	1000円	約400個 (70g)
C	1500円	約600個 (105g)

店によって袋の大きさは様々ですが、ビーズの単価はどれも似たりよったりで、 どこで買うのでもよいかなあというところですが、 ここに、何事もきっちりとしないと気が済まない今回の主人公 M 君が登場します。 そもそも分量の「約」というのは何事だと、サンプルを取り寄せて数え始めた彼を、 誰にも止めることはできません。結果、

B店の袋には 406個、C店の袋には 610個入ってた！

そうな（これがその店が売っているすべての袋に通用すると思い込んでしまう彼の単純さはとりあえずおいておきます）。せっかく苦労して得たデータなんだし有効に使わないと意味ないっす。 と彼、最近どこかのブログで読んだ数理最適化という手法を使ってこれを解くことにしました。 A、B、C から一袋購入すると、ビーズと費用が「セットになってやってくる」。 こう考えるとこれは 「重ね合わせ」タイプ のモデルです。

さて、M君、自分で苦労して得たデータを入れて解きました。 答は「C店の袋だけ4つ買う」です。 データ取りも、定式化も慣れない中あんなに苦労したのになんだか面白くない。 A,B,C 全部取り混ぜて買う、とか苦労に見合った思いもよらない答が出ればよいのになあと思いつつふと気がつくと机の上にビーズが一個転がっているのを見つけました。 どうやら B店の袋にあったのを一つ数え上げ忘れていて、B 店の袋のビーズの個数は都合 407個 だったようです。きっちりした彼のことなので、最適化のデータを 406 から 407 に変更して、数理最適化をやりなおしてみました。 するとどうでしょう、がらっと答が変わってしまいました。 沢山買っていた C 店の袋は一切無視して、「B 店の袋を6袋」という答です。 入力はわずかしか変えてないのになぜこんなことが起きるのかと彼はＰＣを前に首をひねっています。

M 君、自分の業務に数理最適化を積極的に役立てるのはとても素晴しいのですが、ちゃんとした予測を立てずに計算を走らせるだけでは機械が出す結果に振り回されてしまいます。最初は結果を想像しながら手を動かしてみて計算機の答を「評価」してやるべきですね。 B 店の袋と C 店の袋で1円あたりで買えるビーズの個数を計算してみましょう。最初の設定だと B 店の袋では 406個/1000円 = 0.406個/円なのに対して、C店の袋では 600個/1500円 = 0.4067個/円と僅かに多い。 じつは数理最適化がC 店の袋をすべて買うべしとしていたのは、この差に反応してのことでした。 その差がB 店の袋にビーズが一個余計に入っていると逆転されてしまうくらい僅かだったので、 B 店の袋のデータを修正すると今度は B 店の袋をすべて買う、という答になった、というわけです。 そんなに固いこと言わずにC 店の袋でもそんなに悪くないんだから派手に変える必要ないじゃないかね？ それは人間の適当な（実は別の判断基準を導入している）発想というもので、 数理最適化は一旦 C 店の袋よりも B 店の袋の方がコストパフォーマンスが良いと判明し、 B 店の袋で予算を使い切れるとわかったら、C 店の袋を一つも買いません。 そうでなければ、「最適解を見つけよ」との命令に忠実でないことになってしまうから。

非常に単純なケースで説明しましたので、 何をあたりまえのことを言ってるんだと思われるかもしれませんが、 これは頭で追い切れないくらい複雑な問題についても起き得て、 時折数理最適化ユーザーを惑わすので注意が必要です。

それほどデータは変化させてないのに・・・

• 「先月はこのポンプが動いてたけど、今月は全く動かない結果になったぞ!」
• 「先月まで掃除ばかりしてた人が今月は掃除を全くやらなくなったぞ!」
• 「ポートフォリオががらっと変化したぞ！」

一体どうしたんだ？といった具合。

これは多くの場合拮抗した結果（目的関数値）を出す、様相の違う答が複数存在することを示唆しています。 ビーズ問題の場合、「B店のみ買う」「C店のみ買う」、という全然違った二つの答がもたらす結果の差は、二千を超えるビーズの個数にして数個でした。 この二つの答がいわば「水面下」で争っていて、 数理最適化は僅かなデータの差で一番に来たものを拾いあげて報告するので、 結果だけ見ているこちらはびっくりさせられるわけです。

掴むのは常に1番の答だけで 2番を掴まない、 というのが数理最適化アルゴリズムの「精度の良さ」とか「厳密性」というもちろん誇るべき性能ですが、 選ぼうとする答のもたらす結果が僅差である場合、 ときに人を惑わすことがあるのは知っておいて頂いて良いことだと思います。 特にスケジューリングなどに多いのですが、実務の現場でははっきりした良し悪しがつけられない答が大量に発生するので、厳密な１番に拘らずにキーワード検索のように最適解の周辺の答 2,3 個をなんとなく表示してくれている方がよほどありがたいのになあ、と思うことも多々あります。 ただいかんせん、現在スタンダードな数理最適化アルゴリズムの多くは 「最適でないものを早い段階で削る」という動き方をして速度を稼いでいますので、 これはちょっと先のことになるかもしれません。 将来はぜひこういう複数解提案型アルゴリズムの普及に期待するとして、 「厳密すぎる」アルゴリズムに対するユーザー側には、データを変化させて沢山の答を出して目を慣らしておく、「前回の答と大きくは違わない」といった制約を入れる、目的関数を工夫してあり得る答に差をつける、といった自衛策が必要になります。このあたりはまた別の機会にお話ししましょう。

さて、次回は予算上限を変化させて、まさにM君が望んでいた「面白い答」が出るようにしてみます。

居酒屋シフトモデル化いろいろ (3. 「対応付け」タイプの適用)

前回は働き方(シフト)のパターンを列挙して、重ね合わせのモデルを解くことで 必要な人数を手当するために各シフトパターンを割り当てるべき人数を次のように明らかにしました。

あとは、12人のスタッフ A ～ L にどれを割り振るかで、このモデルは 少し前の記事 で紹介した「対応付け」タイプそのものになります。 この記事で紹介している人に仕事を割り合てるケースと全く同じ構造で、 あるパターンに対して対応付けられる人数を重ね合わせモデルが教えてくれた数(パターン1 には 4人、パターン3 には 2人 ...)に制約すればよいのです。 対応付けられる人数 0 と出たパターン2は省いて描いています。

モデルの骨組みができたらあとは個別の制約です。 お客さんからは

1. A さんは午後の勤務ができない(結局Aさんはパターン1しかできない)
2. 昼の繁忙期をカバーするシフト(パターン3)には新人(I,J,K,L)を割りあてない
3. 仕込み時期の朝のシフト(パターン1)は教育のため、新人2人と旧人2人で担当する

といった制約が与えられました。 そもそも 3 番目の制約については、マス目タイプの場合にはどうやって表現してよいのやら見当すら付きにくいのですが、人とシフトの「対応付け」タイプならば大丈夫です(数式での表現が気になる方へ:パターン1と新人達(I,J,K,L)を結んでいる線のうち、正確に 2 本が 1になる(活きる)と制約する)。結果は以下です。

どうでしょう、確かに満たす答になっていますね。 ではスケジューリングはすべて「マス目」ではなく 「重ね合わせ」 + 「対応付け」 すると万事大丈夫かというと、さにあらず。 一時は満足してくれていたお客さんが

「12:00 の繁忙期の時間帯に新人が 2人も交じっているのはちょっと。。。」

とか言いだすと、話はあっという間に荒れ模様に。 朝のシフトパターンを新人2人で担当させる、というのはお客さんの要望として与えられたもので、 4 時間勤務であることの帰結としてそうなるんですよ、とまずは落ち着いてお伝えします。 ここでお客さんの要請が矛盾していて困るとか文句など言っていては数理最適化のプロとしての経験を疑われます。 そもそも答を見ないで何個も制約を言って互いに矛盾しない方が珍しいことで、 要請の矛盾に気付くことができるのが数理最適化の意義とも言えるのです。 まあそれはさておき、しばらく黙って考えていたお客さんがこう切り出したのには我々も不意を突かれます。

「そもそも新人についてはまずは 3時間勤務にするのがよいかもしれないと思うんですが。。。」

うう、これって足りない人を補うために 5 時間勤務も追加されるっていうことかな、するとシフトパターンが増えるのでパターン列挙まで戻らねばならないなあ、これならいっそ「マス目」タイプの方が簡単かもしれない。。。などと逡巡しつつ我々の仕事は続きます。

このように数理最適化では、同じ問題に対するモデル化の方法が複数あって、 それぞれの得手不得手が分かれています。 このケースのようにマス目が結果だから「マス目」タイプが最善、とは限りません。 ぱっと見、手に負えないような問題が別の見方をすると、すきっと解けるということはままあって、 これがモデル化という作業の醍醐味の一つです。一方でお客さんにとっては大したことには見えない要請が一つ増えた途端に精緻に組み立てたモデルが形無しになってしまう、ということもままあります。まあ実務は数理最適化モデルのタイプなど気にせず移ろってゆくものですからそれもやむなし。 我々ができる最善は複数のモデル化の方法に通じて対応力を身につけること、 そしてモデル化の限界といった不都合な話を含めてお客さまときちんとコミュニケーションと取ることでしょうか。そのコミュニケーションのツールとして、この数理最適化モデルのタイプ分けと「絵」が使えればよいな、と手前味噌ながら考えております。

居酒屋シフトモデル化いろいろ (2. 「重ね合わせ」タイプの適用)

前回は最低限の要件から出発して、「勤務は連続」という「常識」を制約の形で入力し、まともなシフトの導出までたどり着きましたが、今回は発想の方向を変えてそもそもどんなシフトが許されるのか、まずは考えてみましょう。 「連続」という制約が効いて、許されるシフトは意外と少なく、 9:00 から 16:00 の連続勤務で 4 時間の勤務パターンは次の 5 つしかありません。

こういうパターンの働き方をする人を何人か「重ね合わせ」て必要人数、すなわち

を実現する方法を数理モデルを使って求めましょう。 重ね合わせ(人数の足し算)の結果と各時刻の必要人数の差を最小化する、次のようなモデル化が可能です。

このモデルはまさに「重ね合わせ」タイプで、時系列がからむところも 重ね合わせによる生産計画問題 と同じです。解くと といった具合に　1 ～ 5 の各パターンに (4人,0人,2人,2人,4人) を割り合てれば丁度人数が満たせることがわかりました。 この人数構成で供給している労働力を積み上げ表示してみたのが次のグラフ(同じパターン毎に色分けしてみました)です。 確かに各時間帯の所要量を満たしていることがわかります。

あとはこのパターンを適当に 12人に割り振れば前回の結果と同様のものが得られます。

前回に紹介した、制約を追加して解を絞り込んでゆく方法と、 あり得る解の列挙から出発する今回の構成的な方法は、 数理最適化モデル化の手法として対になるものです。 例えば下の絵の白地の部分を通る「経路」が許される解だとしましょう。

前回の「解を彫り出す」やり方は、 次のように制約(青い領域)を追加して白地の部分を浮かび上がらせることに相当します。したがって解の領域の形が複雑だと、必要な部分を浮かび上がらせるための制約はかなり増えてしまいます。

さらに無駄な制約も現れます。

左下の青い四角に対応する制約は他の制約にすっぽりと含まれてしまうので不要なのですが、モデル化の時点でこういう重なりに気づくのは数学的にもかなり難しい。大抵の場合まずは安全サイドに制約を加えておこうとなってしまいますのでさあ大変。単純な結果に不釣り合いに「重たい」制約だらけの問題を解くことになりかねません。

一方で今回の構成的な方法は、白地の部分に「経路」のサンプルを複数描いてしまって、数理モデルに外から与えてしまう、ということに相当します。

この方法であれば、解のあり得る領域の形の複雑さが味方して、考慮すべき「経路」の種類や数が少なく済み、手間なく結果を得ることができます。

制約を追加しても追加しても、 出る答が実際的ではないのかお客さんが首を縦に振らない。

「では、あり得る答をちょっと幾つか作って見せてもらえますでしょうか？」

「やけ」になっているみたいですが、 実はこれがきっかけで「列挙+重ね合わせ」の打開策が開けたり、 といったこともあるのです。

さて、解き方の話で進めてきましたが、 この数理最適化モデルの結果の意味付けは前回と若干異なっています。 前回の設定が 12人 のメンバーにどのシフトを取らせるかという、 現場のオペレーションの問題だったのに対して今回は そもそもどういう働き方をする人をそれぞれ何人募集すればよいのかという現場を離れた要員計画、 大袈裟に言うと経営サイドの問題になっていて、 前回の設定では前提条件になっていた 「12人(=4+0+2+2+4)」という人数が結果として導かれています。

• 「こんな人数で現場を回せだなんて本社は何にもわかっちゃいない」
• 「人数をこんなに投入してもまだ現場のパフォーマンスが思ったように向上しないんだよなあ」

一定サイズ以上の組織の様々な局面で聞かれる声だと思いますが、数理最適化ならある程度定量的な裏付けを持つ人員の配置が可能です。最適化を現場と管理サイドの「コミュニケーションツール」として用いる手もあるという事をここで申し添えておきたいと思います。

話が大きくなってしまいましたが、とはいえ、現場のオペレーションには所要人数がわかっただけでは不十分でもっと細かい話の考慮が必要ですね。A さんは夕方の勤務ができない？了解です。次回はこのモデルと「対応付け」タイプのモデルを連携させて、このモデルの延長線上で現場のオペレーションを与える結果を得ましょう。

居酒屋シフトモデル化いろいろ (1. 「マス目埋め」タイプの適用)

数理最適化問題のタイプ分けのご紹介が一通り終わったところで、 これらを用いてよく実務で現れる数理最適化のモデルの組み立て方について具体的に解説しましょう。 オフィス街でランチ営業しているある居酒屋のアルバイトスタッフ 12 人の 勤務シフトを決定する問題を解いてみます。彼らの勤務は一日 4 時間で出勤時間は 朝 9:00 から夕方 16:00 の間とします。

一時間ごとに、現場を回すために必要な人数がおおむね次のようにわかっているとします。 朝方は 4 人、昼時に向けてじわじわと忙しくなり、 昼時に 8 人というピークを迎え、そして同じ形で減衰しています。

結果のシフト表は人と時刻のマトリックス、他ならぬマス目ですから、 まずは「マス目埋め」タイプとしてモデル化してみましょう。 「マス目埋め」タイプの紹介記事 での各列のインデックスを「週」を「時刻」と解釈すればほぼモデルは同じ。 勤務は 1 種類(するかしないか)、なのでかなり単純です。

果たして結果は? 数理最適化では勤務する/しないを 0 と 1 で表現しますが、 1 と出たところを塗りました。

確かに各人の勤務は丁度4時間、縦に見たときの必要人数も満たしています。 こういう結果に直面した場合における、率直な心情を人間代表として数理最適化にぶつけるとすると次のセリフになるでしょうか。

「人数が居れば、勤務時間を満たせば、良いっていうもんじゃない !」

先日の記事では偏りが気になる、といった程度でしたが今回は「使えない」 度合いがパワーアップしています（例えばＢさんとかひどいものです）。 常識的に各人 4時間は連続して働く、 すなわち「1時間外してまた戻ってくる」といった勤務があり得ないことを数理最適化モデルには教えてやる必要があることがわかりました。 こういうときに我々が繰り出すのが、数式で実務的な制約を表現する「小技」です。 古くから様々なテクニックが知られており、大抵の実務的な条件は適宜余計な変数など定義が必要な場合がありますが一次式に書き下すことができます（ちょっと数式っぽくなるので詳細は別の機会に）。 ここでは「一度帰ったら職場に復帰してはならない」という制約を入れることにしましょう。 具体的には横に連続したマス目が 1 (勤務) -> 0 (非勤務) という並びになっているならば、 その右にはすべて 0 が並ぶ、という制約を入れます。

この制約と各人の勤務時間が 4時間であることを合わせると 所望の形の勤務形態となるはずです。

今度は無事、意図した形のスケジュールが出力されました。 このように「マス目埋め」タイプのモデルは、基本の縦と横の制約のみが入っている状態だと 解の自由度に比べて制約が少ない(解の自由度は行と列の数の積ですが、制約の数は和)ので通り一編の答はぱっと出すことができますが、実務的に使えるようにするには様々な小技を駆使した制約を追加して 所望の答をいわば「彫り出す」操作が必要になります。

次回は対照的に「彫り出す」やり方から「組み立てる」やりかたで同じ問題を解いてみましょう。 「重ね合わせ」タイプの出番です。

「対応付け」タイプのモデル:仕事アサインと座席表問題

人に仕事をアサインしたり、車に荷物を割りあてたり、 人に商品をおすすめ(レコメンド)したり、といった問題は 数理最適化の重要な応用の一つで、 これらは次の絵のような構造を持つ「対応付け」タイプのモデルで 記述されます。

「人」や「車」が左の○、「仕事/商品」や「荷物」が右の□。 線分は対応付けの「可能性」を示していて、 仕事のアサインで言えば「人」と「担当できる仕事」を結んでいます。 対応付けタイプの数理最適化を解くことは、 線分のいずれかを取捨選択することに対応します。

「対応付け」タイプのモデルの最も基本的な制約は、 各○が対応付けられてよい数、 レコメンドで言うと各人に対して商品をおすすめすべき数で、 これは次のように左の○から出ている線分の根本に次のような注釈を加えて記述できます。

数理最適化は対応付けられる「□」側の事情も同時に考慮できます。 仕事の割り当ての場合には誰かが選択した仕事を別の人は担当できない、 人に店をレコメンドするのでしたら、 店の容量以上のレコメンドを集中させてはならないといった 事情を右の「□」の根本にやはり注釈を加えて記述しましょう。

対応付けの善し悪しを決める値を線分上に定義しておきます。 仕事のアサインだったら各人の仕事の「希望度合い」 レコメンドだったら「おすすめ度合」といった量を定義しておきます。 3人の仕事のアサイン問題を具体的に記述してみました。 各人が選べる仕事も1つだけ、仕事の定員も 1名とします。

希望度合いの合計が最も大きくなるよう、数理最適化が導いた答は次です。

「最適化」と言いながら、 Aさん、Bさんについては第二希望の仕事がアサインされています。 これは Aさん、Bさんが第一希望を担当する場合のメリットより C さんに第一希望の掃除以外を割り当てる損失が上回るため。 数理最適化の単細胞な損得勘定の結果なので調整は必要ですが、 この単純なモデルでも仕事が競合している場合には、互いの希望度合いと担当可能性が 影響し合ってしまう、という現実を写し取ることができています。

対応付けモデルが考慮できる制約はこれだけではありません。 実務的なケースによく現れる「対応付けの結果に対する制約」という種別を紹介しましょう。 ある小さな会社の社員旅行の幹事さんの悩み、席割り問題をやってみます。 参加人数の30名分の席を確保できたのですが、 取れた指定席が通路を挟んで微妙な感じに分かれています。

社員は新人5名、若手15名、年長者10名という世代構成です。 どこに座らせれば良いでしょうか。 世代が似かよった人が近くに居ると会話が進むよなあと考えた幹事さん、 同じ世代に属する人の会話の頻度を 3 として、世代が一段階違うと 頻度が 1 減る、という少々強引な数値化を考えました。 例えば新人同士は会話の頻度が 3、若手対年長は 1 つ減って 2, 新人対年長は(世代が二つずれているので) さらに減って1、といった具合です。 こうしておいて 「会話の頻度が高い同士を物理的な距離が近い座席に割りあてる」 という制約を考えました。

「人」を「座席」に割りあてる点で基本的な構造は仕事のアサインと同じですが、 対応付けの結果全体の様子を制約する「会話の頻度の高い人同士を近くに」という 要件が入っています。 このタイプの制約が入ると問題はかなり難しくなり、 厳密な最適解を求めることは簡単でなくなってしまうのですが、 幸いこのタイプには簡潔な数学的表現 (どうやるのか気になる方へ：この制約は二次式を使うと簡潔に表現できます) があるので、数理最適化ソルバーに実装すること自体はかなり簡便にできますし、 この程度の規模ならば一分程度で結果が出ます。 どの程度制約が満たされるかはわからないので、 ここでは制約を満たす度合いを数値化して最小化してみました。 次が数理最適化が導いた座席表です。

問題のセットアップは若干面倒でしたが、得られた結果は直観的でなるほど、 各世代の人をまとめて配置する結果になっていますね。 ただ、気持はわかるのですが新人を「半島状」に配置してできるだけ他の社員と接触させない、隔離した感じになってしまいました。 社員旅行は新人との交流を深めるといった意味もあるんだよなあと幹事さんはさらに考えて、 新人同士が固まってしまわないよう、 「新人同士だけについては特別に席を極力遠くすべき」 という要件を付け加えてみることにしました。 (これも数式表現が気になる方のための蛇足ですが、 これは新人同士についてだけ会話の頻度を示す指数を 負の大きな数にすると実現できます)。 以下、得られた結果です.

新人が固まるのは避けられて、先輩社員の側に配置されました (左上のブロックに居る二人はちょっと可哀想ですが)。 ただ、最初にモデルを考えていたときには思いもよらないことでしたが 「極力遠く」という制約が災いして、新人が隅っこになっています。 これは「交流」という意図からは外れますね。 では新人は「へり」にやらないように対応付けの可能性を変更する（対応付けの絵で新人と隅っこの座席を「線」で結ばない）、 あるいはここまで来たら人手で細工すれば十分かもしれません。 まあ、いずれにせよ数理最適化のアシストでまずまずの座席表ができそうではあります。

「思いもよらない」なんてモデルを作った立場なのに無責任な？ 最後まで数式できちっと片付けるべき？ ええ、数理最適化モデルや解法アルゴリズムを実装している我々自身も 特定のデータを与えたときの数式モデルの結果を予測しきることはできないので、 バランス感覚が要求されるこうした問題の場合、 「黙って座ればぴたりと当たる」といった風にはならないことの方が多いのです。 じつは微妙で個別的な要件を実現するために「最後は手で修正」といったこともかなりあります。 それじゃあ最適化の役割はどこにあるのかって？ そのあたりはまたゆっくりと別の回でお話ししましょう。

営業マンの担当区域の割り振り、商品の棚割り、ゲームの対戦表のスケジュールなど、このタイプのモデル化を知ると数理最適化できそうなネタは身の回りのそこかしこに転がっている気がしませんか。 「対応付けの結果に対する制約」まで考慮すると適用範囲はぐっと広がります。 例えば棚割りは上の座席表とほぼ同じ考え方で表現できますし(併売がよく行われる商品間は 座席のケースでの会話の指数が高い、というのと同じ） 対戦表スケジュールでは、ある試合に割り当てられた二人の強さの差が一定以下、 といった制約を考慮することができるようになります。

さて、ここまでで数理最適化モデルの 4 タイプ (重ね合わせ、保存、マス目埋め、対応付け)の紹介が一通り終わりました。 今後も数理最適化モデルのよもやま話を続けますが、 アルゴリズムやモデル化の手法などを紹介するにあたって これらのタイプ分けの話に立ち戻って言及させていただこうと考えています。