数理最適化を極めたい

以前書いたたかしくん記事で、数理最適化の面白さに気づいてしまいました。
今見直すとずいぶんとクレイジーな記事を書いているなと気づきます。
今回はpulpを使って生産ラインの最適化をやってみようと思います。

状況設定

追い込まれるたかしくん

たかしくんが勤めているTAKAHASHI Corpは、4つのプロテイン製品を生産している。
たかしくんはある日、急遽上司に呼び出され、3日後までの生産計画を作ることを命じられた。
作る製品4種類それぞれには特徴があり、原料同士の相性・危機の清掃・スイッチなどで、「これを作ると次これは作れない」という組み合わせがあるそうだ。

TAKAHASHI Corpが持っている生産ラインは3つ。
ラインの性能差や、ラインと製品との相性もあるため、一日で製造できる量もまちまちだ。
調査によると、一日で作れる量は次の通りらしい。

最終的な製造計画のイメージは次の通り。
どのラインでどれを作るか。前後工程の相性もある以上、パズルを全力で解くため、
たかしくんは必死にExcelと向き合うのであった・・・。

生産ラインの条件を変数にする

pulpを使って数理最適化してみます。
基本的にはたかしくん記事やこちらの記事を基に作成しています。
さきほどのテーブルを条件として変数定義します。

将来的にはCSVを読み込ませて定義できると楽そう。

!pip install pulp
from pulp import *

# 何日以内に、何をどれぐらい作るか
num_of_produce_dates = 3
aim_dict = {"a":7,"b":6,"c":3,"d":3}

# 組み合わせの禁則ルール
product_banned_combination_info_list = {"a":["b","d"],"b":["c","d"],"c":["d"],"d":["a"]}

# どのラインで、何をどれぐらい作れるか
line_info_dict = {"A":{"a":5,"b":3,"c":1,"d":0},"B":{"a":3,"b":0,"c":1,"d":2},"C":{"a":1,"b":2,"c":1,"d":1}}

後続の作業に必要となるため、itertoolsを使って「いつどこでなにを作る」という情報と、変数番号との対応表を作ります。
リスト×リストの組み合わせが便利に行えるようです。
この記事がすっごく便利。

import itertools
itsu_dokode_naniwo= list(v1 for v1 in itertools.product(range(0,num_of_produce_dates,1),list(line_info_dict.keys()), list(aim_dict.keys())))
hensu_taio = list((i,v2) for i,v2 in enumerate(itsu_dokode_naniwo))

中身はこんな感じ。ここ辞書型の方が良いのかまだ検証できておらず。
リファクタリングちゃんとやりたい。

最適化条件の定義

今回必要な制約条件は3つ。

①特定の日、特定のラインでは、一種類のモノしか作れない。
②2ライン合計の生産量が、求められる生産量を上回る。
③後続禁止の組み合わせが存在する。

これらを実装していきます。

まずは変数の定義。0-1のInteger型として定義。

m = LpProblem() # 数理モデル
#変数名
x = [LpVariable('x%d%s%s'%(i,d,n), lowBound=0, upBound=1,cat="Integer") for (i,d,n) in itsu_dokode_naniwo]
m += lpSum(x) # 目的関数：なるべく稼働させないことを優先して

制約条件①「特定の日、特定のラインでは、一種類のモノしか作れない。」は次の通り。

#同じ日に
for dy in range(0,num_of_produce_dates,1):
    #同じラインで作れるのは1種類以下
    for l in list(line_info_dict.keys()):
        m += lpSum(x[k]for k,(i,d,n) in hensu_taio if (i,d) == (dy,l)) <= 1

制約条件②「2ライン合計の生産量が、求められる生産量を上回る。」
制約条件③「後続禁止の組み合わせが存在する。」は両方とも製品軸なので、製品軸でfor文をぐるぐるしました。ただ、forの入れ子になりすぎているのでもっと賢いやり方ありそう。
知見求む。

for p in list(aim_dict.keys()):
    # 制約条件②
    m += lpSum(x[k]*line_info_dict[d][n] for k,(i,d,n) in hensu_taio if n == p) >= aim_dict[p]

    # 制約条件③
    #後続で続いてはイケないものを確認
    for bp in product_banned_combination_info_list[p]:
        #連続した日に
        for dy in range(0,num_of_produce_dates-1,1):
            #あるラインで
            for l in list(line_info_dict.keys()):
                #組み合わせで作っちゃだめよ
                m += lpSum(x[k] for  k,(i,d,n) in hensu_taio if (i,d,n) == (dy, l, p) or (i,d,n) == (dy+1,l,bp)) <= 1

最適化計算して整理

ソルブしたあと計算結果を吐き出させます。
ここも将来CSVで吐き出させるとかやりたい。
m.statusは1なら計算成功。他は基本失敗。このページを参照しよう。

m.solve()
print(m.status)

#見せるようのデータフレーム
import pandas as pd
df_line = pd.DataFrame(columns=list(line_info_dict.keys()),index=range(num_of_produce_dates))
df_prod = pd.DataFrame(columns=list(aim_dict.keys()),index=range(num_of_produce_dates))
df_line.fillna("-")
df_prod.fillna("-")

ans_list = []
ans_list = [(i,d,n) for k, (i,d,n) in hensu_taio if value(x[k]) > 0]
res = {"a":0,"b":0,"c":0,"d":0}

for i,d,n in ans_list:
    df_line.at[i,d] = n
    df_prod.at[i,n] = line_info_dict[d][n]
    
display(df_line)
display(df_prod)

displayの結果はこの通り。
上は生産計画、下は各製品の日ごとの生産量。
a,b,c,dいずれも7,6,3,3が生産目標に対し、8,6,3,3作れてますね。

今回a,bが癖ありで、次に作れる製品にかなり制約がありました。
aは基本最後に作ろうね、ということみたいですね。

こうしてたかしくんは無事、生産計画を作り終えたのでした。めでたしめでたし。

ちなみに

3倍の生産量を3倍の期間で

ここからはおもちゃタイム。
3倍の期間で3倍量作るってなったらどうなるんだろう、と思い実験。
条件と結果だけ示しますね。

!pip install pulp
from pulp import *

# ここを全部
num_of_produce_dates = 9
aim_dict = {"a":21,"b":18,"c":9,"d":9}

# おなじ
product_banned_combination_info_list = {"a":["b","d"],"b":["c","d"],"c":["d"],"d":["a"]}

# おなじ
line_info_dict = {"A":{"a":5,"b":3,"c":1,"d":0},"B":{"a":3,"b":0,"c":1,"d":2},"C":{"a":1,"b":2,"c":1,"d":1}}

結果。なんかのびのび作っている感じがしますね。休みの期間を設けるほどの余裕。
a,b,c,dそれぞれ21,18,9,10作っており余裕の表情です。

3倍の生産量を3倍のライン数で

今度は期間は3日間で同じとし、ライン数を9本にしてやってみます。
スペックはA,B,Cそれぞれ全く同じものが増設されたと仮定します。
贅沢ですね。

!pip install pulp
from pulp import *

# 期間同じ、目標だけ3倍
num_of_produce_dates = 3
aim_dict = {"a":21,"b":18,"c":9,"d":9}

# おなじ
product_banned_combination_info_list = {"a":["b","d"],"b":["c","d"],"c":["d"],"d":["a"]}

# ライン3倍
line_info_dict = {"A":{"a":5,"b":3,"c":1,"d":0},"B":{"a":3,"b":0,"c":1,"d":2},"C":{"a":1,"b":2,"c":1,"d":1},
                  "D":{"a":5,"b":3,"c":1,"d":0},"E":{"a":3,"b":0,"c":1,"d":2},"F":{"a":1,"b":2,"c":1,"d":1},
                  "G":{"a":5,"b":3,"c":1,"d":0},"H":{"a":3,"b":0,"c":1,"d":2},"I":{"a":1,"b":2,"c":1,"d":1},}

結果。Iラインが使われずじまい。
aの製造がめんどくさいのか、「とにかく最終日にみんなでつくっちゃおう！片付けめんどくさいから！！」という気概を感じますね。
a,b,c,dそれぞれ21,18,9,10作って成功です。
ちなみにライン数を8に減らすと最適化できなかったので、ギリギリなんだなと。

おわりに

数理最適化おもしろーーーーい！
あとはインターフェースとか上手く作れるといいな。