マッチング理論に関する手法のまとめ

その話ならマッチング理論も選択肢にした方が良いよー、まだ要件が不明確なうちに数理最適化に固執したらダメよー、と言いたくなる社内の提案活動に出くわす。新たな取り組みをしようという気概があるだけ良いことだし、若者よ頑張れなのだけど、まぁ手元で準備しておくか、と。
以下のページから、マッチング理論の部分だけ抜き出して、他の情報と併せて1つのページにした。

イメージアップする記事

読み物としてわかりやすいものと

何なら簡単な実装までわかるものと

教科書的なもの

理論を概観するなら上記が一番よさげ。

あとは大学の先生の説明も。安定マッチングの理論を活かして推定量が作れるのか？

実装：Rによるライブラリ

数理最適化・グラフ理論によるアプローチとの違い

ザックリ見るならこの辺り。
ちなみに数理最適化って何？という人は数理最適化・線形計画法（Operations Research）の方にある記事とかリンクを見れば良いかと。

https://www.kurims.kyoto-u.ac.jp/~kenkyubu/kokai-koza/H22-iwata.pdf

目的（関数）や制約（条件）が複雑で、数式で定義して計算処理に入れないと厳しい問題なら、自由度の高い数理最適化の適用になる。しかし、多くは整数計画法（整数、今回の場合は0-1の二値）であり、問題のサイズが少し大きくなるだけで計算量の壁にぶち当たる。整数変数の一部を実数に緩和したり、遺伝アルゴリズム的に近似解を求めたり、諸々の工夫は出来なくはないけれど、それらの工夫もやりすぎると、元々の問題とのギャップ、後での解釈とか、運用面とかが大変になる。
可能なら、業務上の要件を、データの加工や特徴量の作成といったフェーズで吸収して、マッチング理論による解法に持ち込んだ方が、数理最適化より現実的な求解速度で、納得できる解を安定的に求められる。問題の解釈としてGSアルゴリズム（DAアルゴリズム）だとさすがに合致しないというものなら仕方ないけれど。
手元で学生が勉強するような小規模な問題なら、どちらでもなんとかなるけど、現実の業務で扱う大規模な問題は、もう少し考えたい。

他の情報を見たい方は、目次ページへ
仕切り直しで収集情報の整理から｜くすぐったがり｜note