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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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