とある会社の組織再編を数理モデリングで解決する話

Supershipグループ Advent Calendar 2021の18日目の記事です。

はじめに

はじめまして、@nao_omotです。Supership株式会社でデータ分析の仕事をしています。先日、『Pythonではじめる数理最適化 -ケーススタディでモデリングのスキルを身につけよう-』を拝読したのですが、内容がわかりやすく大変勉強になりました。そこで、さらなる理解の定着を目指して、この本の内容を参考にした架空の物語を作成してみました。長編ですが、最後までお読みいただけると嬉しいです。

構成は次の通りです。数理最適化の理論・アルゴリズムがメインというよりは、要件整理$\rightarrow$数理モデリング$\rightarrow$実装$\rightarrow$検証といった、課題解決のステップを意識した構成になっています。
（注意：すべて架空のお話です。実在する人物・組織等とは一切関係ありません）

　1. 導入
　2. 事前情報
　3. 要件整理
　4. 数理モデリング
　5. 実装
　6. 結果検証

1. 導入

とある会社のお話。ぼくの所属している「データ分析してみる課」の組織再編が近々行われるらしい。以下は、上司の河内課長とのやりとり。

課長：「今のチームをいい感じに再編成をしたいんだけど、ちょっと手伝ってくれない？」
ぼく：「組合わせ最適化問題ですね。簡単なモデリングで解決できますよ」

ということで、河内課長の希望通りのチームを編成することがこのお話のゴールになります。

2. 事前情報

現在「データ分析してみる課」には、課長を除く22名のデータサイエンティストが在籍しています（下記表）。各メンバーにはこの会社でのみ（・・）通用する３つのスキルポイントが定義されており、それぞれスキルポイントが高いほどデータサイエンティストとしての能力が高いことを示しています。

• データサイエンス力（DS）
• データエンジニアリング力（DE）
• ビジネス力（BZ）

また、この課にはリーダー気質があるメンバーが数名おり、対応するメンバーにリーダーフラグが立っています。

python3

# カラム情報
columns = ["id", "name", "skill_ds", "skill_de", "skill_bz", "leader_flg"]

# メンバー情報
ueno = [1,"上野", 80, 20, 30, True]
ishizawa = [2, "石沢", 50, 50, 50, False]
inoshita = [3, "井下", 50, 110, 20, False]
otomo = [4, "大友", 10, 20, 30, False] 
okamoto = [5, "岡本", 50, 10, 120, False] 
kamimura = [6, "上村", 10, 130, 30, False]
higashiyama = [7, "東山", 10, 160, 120, False]
sato = [8, "佐藤", 60, 10, 40, False] 
shiroyanagi = [9, "白柳", 10, 180, 180, False] 
shinpo = [10, "新保", 30, 60, 90, False]
sueoki = [11, "末置", 90, 80, 10, False]
suzuki = [12, "スズキ", 70, 10, 20, False] 
takamoto = [13, "高本", 50, 50, 50, False] 
tamada = [14, "玉田", 40, 100, 30, False]
chen = [15, "チェン", 80, 150, 150, False] 
cho = [16, "チョウ", 10, 120, 70, False]
toyomoto = [17, "豊元", 90, 90, 10, False]
torvalds = [18, "トーバルズ", 200, 200, 200, False] 
nagane = [19, "長根", 60, 10, 150, True] 
vanni = [20, "バニー", 20, 30, 90, False] 
fukumoto = [21, "福本", 40, 40, 40, True] 
lie = [22, "リー", 50, 10, 150, False] 

# データフレームの作成
import pandas as pd
df = pd.DataFrame([ueno, ishizawa, inoshita, otomo, okamoto,
                  kamimura, higashiyama, sato, shiroyanagi, shinpo,
                  sueoki, suzuki, takamoto, tamada, chen,
                  cho, toyomoto, torvalds, nagane, vanni,
                  fukumoto, lie, ], columns=columns,)

	id	name	skill_ds	skill_de	skill_bz	leader_flg
0	1	上野	80	20	30	True
1	2	石沢	50	50	50	False
2	3	井下	50	110	20	False
3	4	大友	10	20	30	False
4	5	岡本	50	10	120	False
...
17	18	トーバルズ	200	200	200	False
18	19	長根	60	10	150	True
19	20	バニー	20	30	90	False
20	21	福本	40	40	40	True
21	22	リー	50	10	150	False

これら情報（表1）をもとに二人の会話が進行します。

3. 要件整理

さて、河内課長の希望通りのチームを編成するためにヒアリングを開始します。まずは、いい感じのチームの定義から聞いてみることにしました。

ぼく：「チーム編成の方針はあるんですか？」
課長：「現在在籍しているデータサイエンティスト22人を2つのチームに分けて、自社プロダクトの開発に特化したチーム（1G）とクライアントのDXを支援するチーム（2G）を作りたいと思っている」
ぼく：「なるほど」

どうやら、在籍メンバーを2つのチームに分けて編成を行いたいとのことです。ここから、1つ目の要件が得られました。
以降、このような形式で河内課長との会話から要件を整理していきます。

【要件1】2つのチームに分けて、各メンバーをどちらかのチームに割り当てる

> ぼく：「そういえば、ぼくがこの前取り組んだデータサイエンティストスキル可視化プロジェクトの結果があるんですけど（表1）、3つのスキルポイントを使うと各チームはどのくらいの数値が必要かわかりますか？」 課長：「そうだな。データサイエンティストとして特定のスキルに偏って欲しくないから、どちらのチームもDS, DE, BZのスキルはメンバー合算でそれぞれ500pt以上は欲しい。ただし、業務の役割を踏まえて1GについてはDEが1,000pt以上、2GはBZが1,000pt以上必要かな」

スキルポイントについては2. 事前情報で定義した通りです。

【要件2】 各チーム、下記のスキルポイントを必要とする
　・ 1G: DS, BZが500pt以上、DEが1000pt以上
　・ 2G: DS, DEが500pt以上、BZが1000pt以上

課長：「ちなみに、チームを編成するときにはどちらのチームにもリーダ候補がいて欲しい」
ぼく：「だれです？」
課長：「上野、長根、福本の3人だ」

リーダー候補の情報は表1のleader_flgカラムに対応します。

【要件3】 各チーム、一人以上のリーダー候補が存在する

課長：「あと、メンバー数に偏りが出てしまうとチームリーダーに負担がかかってしまうので、１チームせいぜい15人までにするべきだろうな」

【要件4】 各チーム、15名以下にする（7名以上にする）

ぼく：「ほかに、考慮するべき点はありますか？」
課長：「そうだな、実はここだけの話、チェンとチョウは関係があまり良くないらしく、チームの士気に影響が出てきそうなんだよな。できれば、別のチームに分けたいと思ってる。同じく、岡本と新保も別のチームにしたい」
課長：「要件はこんなもんかな？ よろしく！」
ぼく：「...」

【要件5】 特定のメンバー2人（岡本と新保、チェンとチョウ）が同じチームに属さないようにする

現実的な話ではなくなってきましたが、これで要件が出揃いました。以上の5つの要件をもとに、チームを編成していきましょう。

4. 数理モデリング

「チーム編成」という課題を「組合わせ最適化問題」と捉えて、得られた5つの要件を数理モデルに落とし込むことにします。まずは、簡単に数理最適化についておさらいします。

（正直、今回のような20人程度のチーム編成なら、モデリングしたところで作業コストの削減にはなりませんが、要件の追加・変更にすぐに対応できるというメリットがあるので、モデリングすることの価値はあると思ってます。たぶん）

4.1. 数理最適化（組合わせ最適化）

数理最適化（Mathematical Optimization）は、決定変数(variable)に関する制約条件のもとで、目的関数（objective function）を最小化（または最大化）する変数を求める手続きのことです。

数理最適化で扱う最適化問題は、集合 $S$、および $S$ から実数 $\mathbb{R}$ への写像 $f:S \rightarrow \mathbb{R}$ が与えられたとき、一般的に以下の形で表すことができます。

minimize \ \ \ f({\bf{x}}) \\
s.t. \ \ \ {\bf{x}} \in S

$\bf{x}$が決定変数、関数 $f$が目的関数に対応します。また、制約条件を満たす解を実行可能解（feasible solution）と呼び、その集合である $S$ を実行可能領域（feasible region）と呼びます。
（ちなみに、$s.t.$はsuch thatではなく、subject toの意味で使ってます。また、$minimize$ も $S$ が無限集合の場合は正確には $inf$ と書くべきですね。たぶん）
また、目的関数の最小値を最適値（optimal value）と呼び、その最適値 $z^*$を

z^* = \text{inf} \left\{\ f({\bf{x}})\ |\ {\bf{x}} \in S \right\}

のように定めると、最適値 $z^*$ を与える最適解（optimal solution） $x \in S$ の集合 $S^*$ を

S^* = \left\{ {\bf{x}} \in S\ |\ f({\bf{x}})=z^* \right\}

のように表すことができます。以上、数理最適化の一般論の話でした。

ところで、制約条件と目的関数が線形で表される線形計画問題は高校数学の「領域の最大・最小」として登場するので意外と馴染みのあるものだったりするのではないでしょうか。また、たとえば最小二乗法も制約条件のない最適化問題とみることもできますし、最急降下法など機械学習の分野においても最適化理論は重要な役割を果たします。

以下に、代表的な数理最適化の典型問題を書いてみます。

• 線形計画問題
• 凸2次計画問題
• 整数計画問題
• 最短経路問題

さて、組合わせ最適化（Combinatorial Optimization）とは、数理最適化のうち離散要素を含む解を求める手続きのことです。上記の例だと、整数計画問題（と最短経路問題）が組合わせ最適化問題の枠組みに含まれます。特に、今回のテーマである「チーム編成」は、整数計画問題の中でも決定変数が0か1しか取らない「0-1整数計画問題」として定式化できます。

整数（線形）計画問題は一般的に以下の形で表すことができます。ここで、変数 $x_j$ は非負整数値をとることに注意します。

minimize \ \ \ \sum_j c_j x_j \\
s.t. \ \ \ \sum_j a_{ij}x_j \leq b_i, \\
\ \ \ x_j \in \mathbb{Z}_{+}

整数計画問題はNP困難であるため、変数の数や領域が大きくなると厳密解を求めることが難しくなります。その場合は近似解法や局所探索法といった限られた計算時間で質の高い実行可能解を求める手法が用いられたりします。

4.2. 数理モデル

では、先ほど整理した5つの要件をもとに、数理モデリングを行っていきます。
まずは、メンバーリスト$M$、およびチーム$T$を定義します。

M
\ \ \ 
(\text{メンバーID})
\\
T
\ \ \ 
(\text{チーム名})

それぞれ、$M$はメンバーIDに対応する1から22の整数、$T$は2つのチーム1G, 2Gを表すものとします。
次に、決定変数 $x$ を定義します。今回のケースでは各メンバーがどちらのチーム（1G or 2G）に割り当てるかを決定する問題を解きたいので、メンバー $m \in M$ とチーム $t \in T$ の組み合わせについて $x_{mt}$ を定義し、メンバー $m$ をチーム $t$ に割り当てる場合 $x_{mt}=1$、割り当てない場合 $x_{mt}=0$ を取るものとして定義します。

x_{mt} \in \{0, 1 \} 
\ \ \  
(m \in M,\ t \in T) \tag{1}

以下、この決定変数をもとに、各要件を制約条件（制約式）として定義していきます（今回のケースでは、目的関数はありません）。

【要件1】2つのチームに分けて、各メンバーをどちらかのチームに割り当てる

各メンバーがどちらかのチームに配属する( = 1つのチームにしか割り当てられない)とのことなので、どのメンバーについても$\sum_t$について必ず1になる必要があります。たとえば、大友$(s=4)$の場合、$x_{4,1G} + x_{4,2G} = 1$ということです。一般化して、次のように書きます。

$$
\sum_t x_{mt} = 1
\ \
(m \in M) \tag{2}
$$

【要件2】 各チーム、下記のスキルポイントを必要とする
　・ 1G: DS, BZが500pt以上、DEが1000pt以上
　・ 2G: DS, DEが500pt以上、BZが1000pt以上

各メンバーのデータサイエンティストスキルポイント $P_{sm}(s \in \{\text{ds}, \text{de}, \text{bz}\}, m \in M)$ を新たに定義すると、各チームのスキル要件を次のように表現できます。

\sum_{m,\ t=\text{1G}} P_{sm} x_{mt} = 
\left\{
\begin{array}{lll}
500 & (s = \text{ds}) \\
1000 & (s = \text{de}) \tag{3} \\
500 & (s = \text{bz}) 
\end{array}
\right. 

\sum_{m,\ t=\text{2G}} P_{sm} x_{mt} = 
\left\{
\begin{array}{lll}
500 & (s = \text{ds}) \\
500 & (s = \text{de}) \tag{4}\\
1000 & (s = \text{bz}) 
\end{array}
\right. 

【要件3】 各チーム、一人以上のリーダー候補が存在する

リーダーの素質があるメンバーリスト$M_{\text{leader}}$を用いて、制約式を以下のように定義します。
$$
\sum_{m \in M_{\text{leader}}} x_{mt} \geq 1
\ \ \
(t \in T) \tag{5}
$$

【要件4】 各チーム、15名以下にする（7名以上にする）

こちらは、【要件3】と似た形で制約式を定義することができます。7人以上15人以下を2つの制約式で表現します。

\begin{align}
\sum_{m \in M} x_{mt} &\geq 7  \ \ \ \ \ (t \in T) \tag{6} \\
\sum_{m \in M} x_{mt} &\leq 15 \ \ \ (t \in T) \tag{7} \\
\end{align}

【要件5】 特定のメンバー2人（岡本と新保、チェンとチョウ）が同じチームに属さないようにする

特定メンバーのペアリスト$M_{\text{pairs}}$を定義し、片方のチームに二人割り当てなければいいので、

x_{m1, t} + x_{m2, t} \leq 1
\ \ \ 
((m1, m2) \in M_{\text{pairs}},\ t \in T) \tag{8}

と書くことができます。これは、たとえばペアリストから特定の2名 $m_1,\ m_2$ を選択し、1Gのチームについて固定して考えると、$m_1,\ m_2$が同時に1Gチームに配属される場合に限り $x_{m1,\ \text{1G}} + x_{m2, \ \text{1G}}=2$となり、制約条件から外れることを意味しています。

さて、一通り数式に落とし込みましたが、この段階でこの数理モデルが解けるかはもちろん自明ではありません。もし解けない場合は要件（制約）を弱めるか、または変更するなどの対応が必要になります（計算量が多い場合は、有料のソルバーを使用するなども考えられます）。ただし、今回はそんなことが起こらないようにもろもろ調整済みです。

5. 実装

上記の数理モデルをPythonで実装して解くことにします。実装の際は、PuLPライブラリを使用します。この章では、簡単にPuLPについて紹介したあと、実装したコードをまとめます。

5.1. 数理最適化ライブラリ（PuLP）

数理最適化問題には、問題を解くためのプログラム (最適化ソルバー) がいくつか開発されており、現在ではそれらを使用することで簡単に最適化問題を解ける環境が整っています。PuLPも数理最適化問題を解くために提供されている無償ライブラリの一つで、変数、制約条件、目的関数等を入力するだけで、最適解を出力してくれます。
（正確には、PuLPは問題を表現するモデリング言語であり、問題を解くのは同梱されているCBCソルバーです。PuLPをインストールすると自動でCBCもインストールされます。たぶん）

PuLPを使用する場合は事前にインストールが必要です。例えばpipインストールの場合、次のコマンドでインストール可能です（参考：Installing PuLP at Home）。なお、モデルの実装の際はver 2.5.1のPuLPを使用しました。

python -m pip install pulp

PuLPを用いた数理モデルの実装手順について、簡単に下記にまとめました。使い方は非常にシンプルで、今回のケースでは大まかに以下の手順で実装しています。

1. ライブラリのインポート
2. 問題の定義（インスタンス生成）
3. 決定変数の定義
4. 制約式の追加
5. 解を求める（ソルバーの実行）

5.2. 数理モデルの実装　

これまでの数理モデルを実装したものを下記に記載します。便宜上、要件の順番を入れ換えて実装しています。

python3

import pulp

#モデルのインスタンス生成
prob = pulp.LpProblem("TeamAssignment", pulp.LpMaximize)

# チームメンバーリスト
M = df["id"].tolist()
# チームリスト
T = ["1G", "2G"]
# メンバーとチームペアリスト
MT = [(m,t) for m in M for t in T]

# メンバーをどのチームに割り当てるかを変数として定義
x = pulp.LpVariable.dicts("x", MT, cat="Binary")

# 要件1：チームを2つに分けて、各メンバーをどちらかのチームに割り当てる
for m in M:
    prob += pulp.lpSum([x[m,t] for t in T]) == 1

# 要件4：各チーム、15名以下にする（7名以上にする）
for t in T:
    prob += pulp.lpSum([x[m,t] for m in M]) >= 7
    prob += pulp.lpSum([x[m,t] for m in M]) <= 15 

# 要件2：各チームのデータサイエンティストスキルポイントの要件を満たす
skill_ds = {row.id: row.skill_ds for row in df.itertuples()}
skill_de = {row.id: row.skill_de for row in df.itertuples()}
skill_bz = {row.id: row.skill_bz for row in df.itertuples()}
for t in T:
    if t == "1G":
        # (ds>=500, de>=1000, bz>=500)
        prob += pulp.lpSum(x[m,t]*skill_ds[m] for m in M) >= 500
        prob += pulp.lpSum(x[m,t]*skill_de[m] for m in M) >= 1000
        prob += pulp.lpSum(x[m,t]*skill_bz[m] for m in M) >= 500
    if t == "2G":
        # (ds>=500, de>=500, bz>=1000)
        prob += pulp.lpSum(x[m,t]*skill_ds[m] for m in M) >= 500
        prob += pulp.lpSum(x[m,t]*skill_de[m] for m in M) >= 500
        prob += pulp.lpSum(x[m,t]*skill_bz[m] for m in M) >= 1000

# 要件3：各チーム、一人以上のリーダー候補が存在する
leader = [row.id for row in df.itertuples() if row.leader_flg==True]
for t in T:
    prob += pulp.lpSum(x[m,t] for m in leader) >= 1

# 要件5:特定のメンバー2人（岡本と新保、チェンとチョウ）が同じチームに属さない
MM = [(5, 10), (15, 16)]
for m1, m2 in MM:
    for t in T:
        prob += x[m1, t] + x[m2, t] <= 1

# 求解
status = prob.solve()
print("Status:", pulp.LpStatus[status])
print()

# 最適化結果表示
T2M = dict()
for t in T:
    T2M[t] = [m for m in M if x[m, t].value()==1]

for t, m in T2M.items():
    print("Team:", t)
    print("Num:", len(m))
    print('Member:', m)
    print() 

上記コードを実行すると、以下の結果が得られました。

実行結果

Status: Optimal

Team: 1G
Num: 14
Member: [1, 2, 3, 4, 6, 7, 8, 10, 11, 13, 14, 16, 17, 20]

Team: 2G
Num: 8
Member: [5, 9, 12, 15, 18, 19, 21, 22]

１行目の Status: Optimal は定義した数理モデルが解けたのかの情報を表しています。今回のケースでは最適解（Optimal）が得られたことがわかりました。各チームに割り振られた人数を見る限り、もっともらしい解が得られたように思えます。
では最後に、ここで得られた結果がきちんと要件を満たしているかを確認していきます。

6. 結果検証

最後の章です。PuLPよって得られた解について振り返り、河内課長の要望を満たしているかを確かめます。問題なければ、河内課長に「データ分析してみる課」の新しいチーム編成案を報告しましょう。

まずは、各メンバーが漏れ・重複なく、いずれかのチームに割り当てられているかを確認します。各メンバーがどちらのチームに配属されたかの情報をメンバーリスト（表1）に結合してresults_dfを作成します。

results_df = df.copy()

# 要件1：チームを2つに分けて、各メンバーをどちらかのチームに割り当てる
M2T = {m:t for m in M for t in T if x[m,t].value()==1}
results_df["assigned_team"] = results_df["id"].map(M2T)
results_df

	id	name	skill_ds	skill_de	skill_bz	leader_flg	assigned_team
0	1	上野	80	20	30	True	1G
1	2	石沢	50	50	50	False	1G
2	3	井下	50	110	20	False	1G
3	4	大友	10	20	30	False	1G
4	5	岡本	50	10	120	False	2G
...
17	18	トーバルズ	200	200	200	False	2G
18	19	長根	60	10	150	True	2G
19	20	バニー	20	30	90	False	1G
20	21	福本	40	40	40	True	2G
21	22	リー	50	10	150	False	2G

上記の表は省略されていますが、不具合なく配属先のカラムが追加されているのが確認できました。
各グループに配属される人数についても改めて確認してみます。

# 要件4：各チーム、15名以下にする（7名以上にする）
results_df.groupby(["assigned_team"])["id"].count()

実行結果

assigned_team
1G    14
2G     8
Name: id, dtype: int64

1Gが14人、2Gが8人ということで、多少の偏りがあるものの、きちんと要件を満たしています。

次に、各チームのデータサイエンティストスキルの要件を確認しているかを確かめてみます。要件はDSスキル, DEスキル, BZスキルいずれも500pt以上で、かつ1GはDEが1000pt以上、2GはBZが1000pt以上でした。

# 要件2：各チームのデータサイエンティストスキルポイントの要件を満たす
results_df.groupby(["assigned_team"])[["skill_ds", "skill_de", "skill_bz"]].sum()

assigned_team	skill_ds	skill_de	skill_bz
1G	600	1030	670
2G	560	610	1010

チーム人数には偏りがありましたが、スキルポイントの要件もきちんと満たしていることが確認できました。

各チームにリーダー候補がいるかも確認しておきましょう。

# 要件3：各チーム、一人以上のリーダー候補が存在する
results_df.groupby(["assigned_team"])[["leader_flg"]].sum()

assigned_team	leader_flg
1G	1
2G	2

どちらのチームにもリーダー候補が一人以上いることも確認できました。ちなみに、1Gのリーダ候補は上野、2Gのリーダ候補は長根、福本となっています。

最後に、特定のペアが同じチームに属さないという要件を確認します。河内課長によると「岡本と新保」および「チェンとチョウ」がそれぞれ同じチームに属して欲しくないとのことでした。results_dfから4人を抜き出して見てみましょう。

# 要件5:特定のメンバー2人（岡本と新保、チェンとチョウ）が同じチームに属さない
# (岡本:5、新保:10), （チェン:15、チョウ:16）
results_df[results_df["id"].isin([5,10,15,16])]

	id	name	skill_ds	skill_de	skill_bz	leader_flg	assigned_team
4	5	岡本	50	10	120	False	2G
9	10	新保	30	60	90	False	1G
14	15	チェン	80	150	150	False	2G
15	16	チョウ	10	120	70	False	1G

問題なく、別チームに所属させることができていますね。

以上、得られた結果が5つの要件すべてについて満たされていることが確認できたので、河内課長にこのチーム編成案を報告します。

課長「いい感じ！」

問題なさそうなので、これにてタスク完了です。おつかれさまでした！

おわりに

ここまでお読みいただきありがとうございます！

数理最適化についてはまだまだ勉強し始めたばかりですが、実際に手を動かしたことでより理解を深めることができました。そして、アルゴリズムの性能や計算の複雑さなど、気になること、興味のあることがさらに増えました。この記事も皆さんの興味を持つきっかけになれば嬉しく思います。

最後に、今回の架空の物語を作成するにあたって『Pythonではじめる数理最適化 -ケーススタディでモデリングのスキルを身につけよう-』の多くを参考にしました。この場を借りてお礼申し上げます。

参考文献

この記事は以下の情報を参考にして作成しました。

• 岩永二郎、石原響太、西村直樹、田中一樹『Pythonではじめる数理最適化 -ケーススタディでモデリングのスキルを身につけよう-』オーム社（2021）
• 梅谷俊治『しっかり学ぶ数理最適化 -モデルからアルゴリズムまで-』講談社（2020）
• PyData.Tokyo Meetup #24 Pythonではじめる数理最適化 [connpass]
• Python言語による実務で使える100+の最適化問題
• PuLP による数理最適化超入門
• 今度こそ？使い物になるフリーの数理最適化（混合整数最適化）ソルバー（付きインターフェース） Python-MIP [Qiita]
• データサイエンティストのためのスキルチェックリスト/タスクリスト概説 [データサイエンティスト協会]

最後に宣伝

Supershipではプロダクト開発やサービス開発に関わる人を絶賛募集しております。
ご興味がある方はSupershipグループ 採用サイトをご確認ください。よろしくお願いします。