難易度：★★★★☆
組み合わせ最適化の中でも実世界において頻出する2部マッチングに注目し、関連する問題が解けるようになることを目指します。ここでは大企業の人事になったつもりで、新卒採用により大人数の新入社員の配属先を決定する業務をこれから行うことを想定します。従来、新入社員の配属先を決める際は、本人の希望や適正、配属先の受け入れ容量などを考慮して人が手作業で割り当てを行っているとします。人数が多ければ多いほどこの作業は工数がかかります。そこでこの問題を最適化問題としてとらえ、最適化を行うことで、作業を自動化して工数の大幅削減を目指します。実際に業務を行うことを想定して、どのようなことを考慮して定式化などを行い、最適化問題を解くのかを学びます。
あなたは大企業S社の人事として働いていて、毎年大量にやってくる新入社員を適切な部署に割り当てる作業を担当しており、手作業では時間がとてもかかり、頭を悩ませています。この作業を早く終わらせる何か良い方法はないか色々調べていくうちにあなたは組み合わせ最適化の存在を知りました。何かと何かを紐づけるマッチングアルゴリズムが使えるのではないかと考えたあなたは早速作業にとりかかりました。
Mission 1
ここではデータ構造としてのグラフについて学びます。与えられたデータに対してデータ構造としてのグラフを作成し、分析を行ったり、可視化する方法を学びます。データの規模感や基本的な性質を明らかにするのが主な目的です。
ここではデータ構造としてのグラフについて学び、networkxやpandasというPythonのライブラリを用いてグラフを作成する方法を学びます。
ここではデータ構造としてのグラフに対する分析の仕方や可視化の方法について学びます。
このTaskではこのMissionで学んだことをまとめます。
Mission 2
ここでは作成したグラフを用いて、実際に最適化を行う方法や結果を可視化して解釈する方法を学びます。このMissionでは、新入社員10人を10個の部署に割り当てる問題を考えます。この問題を2部マッチングにおける典型的な問題である最大重みマッチングとして扱います。2部グラフを考えることでどのような問題が解けるかを実感して、そもそも最適化とは何か、また最適化後どのような結果が出るかを見ることが主な目的です。
ここでは2部グラフの性質や扱い方について学びます。
このTaskではこのMissionで学んだことをまとめます。
Mission 3
ここでは制約条件を考慮して最適化を行いたい時の方法として数理最適化を学びます。このMissionでは新入社員100人を10個の部署に割り当てる問題を考えます。さらに、例えば特定の人たちの配属先は全員異なるように設定するなどの制約を加えた問題を扱います。前回のMissionよりも変数が多く、制約条件も複雑となります。数理最適化ライブラリのPuLPを用いて、目的関数と制約条件の数式による表現方法を学び、特にグラフにおける最適化と比べてその適用範囲の広さを実感してもらうことが主な目的です。
