組合せ最適化で「ものを分ける」

# これなに

ブルーバックスの[離散数学「ものを分ける理論」](http://bookclub.kodansha.co.jp/product?item=0000310274)のくだものを姉妹で分ける問題を読んでちょっとアレンジしました。

# 問題

- 6つのくだものがあります。
- 2人の姉妹で、分けます。
- 各々の価値観は異なります（それぞれ、価値の合計が100になるように、各くだものごとに点数をつけています）。
- くだものは、なるべく分割しないで分けましょう。分割すると、価値はどちらも6割に減少するものとします。
- 各々の価値観で、価値の総和の最小を最大化してください。

# Pythonで定式化して解く

例によって、PuLPで解きます。変数は下記の通り。定式化は簡単なので省略。

参考：[最適化におけるPython \- Qiita](https://qiita.com/SaitoTsutomu/items/070ca9cb37c6b2b492f0)

ライブラリーは、`pip install pandas pulp ortoolpy`でインストールしてください。

```py
import pandas as pd
from pulp import LpProblem, LpMaximize, lpDot, lpSum, value, GLPK_CMD
from ortoolpy import addvar, addvars, addbinvars
def divide(df, rate = 0.6):
   # assert (df[['A', 'B']].sum() == 100).all()
    df['VarA'] = addbinvars(len(df))  # Aが貰う
    df['VarB'] = addbinvars(len(df))  # Bが貰う
    df['VarP'] = addvars(len(df))  # 分割してAが貰う割合
    df['VarQ'] = addvars(len(df))  # 分割してBが貰う割合
    m = LpProblem(sense=LpMaximize)
    obj = addvar()
    val_a = lpDot(df.A, df.VarA) + rate * lpDot(df.A, df.VarP)
    val_b = lpDot(df.B, df.VarB) + rate * lpDot(df.A, df.VarQ)
    m += obj
    m += obj <= val_a
    m += obj <= val_b
    for row in df.itertuples(False):
        m += row.VarA + row.VarB + row.VarP + row.VarQ == 1
    cmd = GLPK_CMD()
    m.solve(cmd)
    if m.status == 1:
        for c in 'ABPQ':
            df[f'Val{c}'] = df[f'Var{c}'].apply(value)
        return value(val_a), value(val_b)
    return -1, -1
```

`divide`は2人の価値の総和を返します。

```py
df = pd.DataFrame([[36, 32], [24, 38], [12, 7], [12, 13], [10, 5], [6, 5]], 
    columns=['A', 'B'],
    index='もも めろん りんご みかん ぶどう ばなな'.split())
print(divide(df))
df
>>>
(58.0, 56.0)
```

|     | A  | B  | VarA    | VarB    | VarP    | VarQ    | ValA | ValB | ValP | ValQ |
|:--- |:-- |:-- | ------- | ------- | ------- | ------- | ---- | ---- | ---- | ---- |
| もも  | 36 | 32 | v000001 | v000007 | v000013 | v000019 | 1    | 0    | 0.0  | 0.0  |
| めろん | 24 | 38 | v000002 | v000008 | v000014 | v000020 | 0    | 1    | 0.0  | 0.0  |
| りんご | 12 | 7  | v000003 | v000009 | v000015 | v000021 | 1    | 0    | 0.0  | 0.0  |
| みかん | 12 | 13 | v000004 | v000010 | v000016 | v000022 | 0    | 1    | 0.0  | 0.0  |
| ぶどう | 10 | 5  | v000005 | v000011 | v000017 | v000023 | 1    | 0    | 0.0  | 0.0  |
| ばなな | 6  | 5  | v000006 | v000012 | v000018 | v000024 | 0    | 1    | 0.0  | 0.0  |

「もも、りんご、ぶどう」（価値58）と「めろん、みかん、ばなな」（価値56）に分かれました。

ちょっと不公平ですね。
分割しても、価値が減少しないものとして、解きなおしてみましょう。

```py
print(divide(df, 1))
df
>>>
(57.499995999999996, 57.500004000000004)
```

|     | A  | B  | VarA    | VarB    | VarP    | VarQ    | ValA | ValB | ValP     | ValQ     |
|:--- |:-- |:-- | ------- | ------- | ------- | ------- | ---- | ---- | -------- | -------- |
| もも  | 36 | 32 | v000026 | v000032 | v000038 | v000044 | 1    | 0    | 0.000000 | 0.000000 |
| めろん | 24 | 38 | v000027 | v000033 | v000039 | v000045 | 0    | 1    | 0.000000 | 0.000000 |
| りんご | 12 | 7  | v000028 | v000034 | v000040 | v000046 | 0    | 0    | 0.458333 | 0.541667 |
| みかん | 12 | 13 | v000029 | v000035 | v000041 | v000047 | 0    | 1    | 0.000000 | 0.000000 |
| ぶどう | 10 | 5  | v000030 | v000036 | v000042 | v000048 | 1    | 0    | 0.000000 | 0.000000 |
| ばなな | 6  | 5  | v000031 | v000037 | v000043 | v000049 | 1    | 0    | 0.000000 | 0.000000 |

りんごを分割して、2人とも57.5になりました。

# 補足

ソルバーとしてデフォルトのCBCではなくて、GLPKを使っています。くだもの2個だとCBCはバグって最適解が出ません。

GLPKは、macOSだと`brew install glpk`でできます。Windowsの人は、頑張ってください。

# lpDot

lpDotは、係数と変数リストでないといけません。

`lpDot(df.A, df.VarA) + rate * lpDot(df.A, df.VarP)`を`lpDot(df.A, df.VarA + rate * df.VarP)`とすると、`rate`が無視されるので注意しましょう。

以上