「Python実践データ分析100本ノック」実践編②最適化問題をortoolpyを用いずに解く

はじめに

書籍「Python実践データ分析100本ノック」の実践編②で最適化問題に取り組みました。サンプルコードではortoolpyというpythonライブラリを用いていたのですが、私はこれを使わずに問題を解いてみました。なぜならortoolpyを使うと、何をしてるかわからないけど結果が得られるのが個人的に気持ち悪かったためです。また、調べてみるとortoolpyは他書籍のためにその著者の方が作ったライブラリで、一般的なものではないことがわかりました。（なお、ortoolpyとともに用いられているPuLPというライブラリは最適化問題を解く一般的なライブラリのようなので、こちらは使うことにしました。）
コードの作成を試行錯誤しながら行った結果、この順でコードを考えていれば、手戻りが少なくできるぞ、と思う順序を整理できました。
そこで、今回の記事では、実際のコードと私が効率が良いと思う最適化問題のコードの作成順序について紹介したいと思います。私と同じようにortoolpyを使わずにPuLPだけで本書の実践編②の問題を解きたいと思った方の参考になれば幸いです。
なお、コードの作成はPuLPの公式ドキュメントとortoolpyのソースコードを参考にして行いました。

実際のコード

第3部：実践編②の第７章「ロジスティクスネットワークの最適設計を行う１０本ノック」

https://github.com/piz3in/Python100knock/blob/main/Part3/Chapter7/chapter7.py

最適化問題を解くコードを考える順序

結論からいうと、次のような順序で考えるのが手戻りが少なくて良いと思います。

1. 解きたい問題を明文化して整理する
2. 問題の記述方法を考える
   1. 制約条件の記述の検討
   2. 変数の定義方法の決定（辞書型にするのか、PandasのDataFrameにするのか等）
   3. 目的関数の定義方法の決定

ここからは、上記の順で具体的にどのようにコードを考えていくかを、ノック68のロジスティックネットワーク設計問題を例にとって説明します。（本問題を解くコードは上に貼った実際のコードのL263以降にあたります。）

1. 解きたい問題を整理する

まずは、解きたい問題を整理します。
具体的には、目的関数、問題の分類（最大化問題と最小化問題のいずれか）、変数、制約条件を文で記述します。

今回の問題ではそれぞれ以下のようになります。

• 目的関数：製品の生産費と各工場からの輸送費の総和

  1. 製品の生産費：Σ(各レーンでの各製品の生産費)*（各レーンでの各製品の生産量）
  2. 各工場からの輸送費：Σ（各工場から各商店への輸送費）*（各工場からの製品の出荷量）

• 問題の分類：最小化問題

• 変数：

  1. 各工場、各レーンでの各製品の生産量
  2. 各工場から各商店への各製品の輸送量（出荷量）

• 制約条件：

  1. 各工場での各製品の生産量が各工場からの各製品の輸送量以上になる
  2. 各工場での各レーンの各製品の生産量が各レーンの生産量上限以下になる
  3. 各商店への各製品の輸送量（入荷量）が各商店での各製品の需要量以上になる

さらに、その他に考慮すべきことがないかをチェックします。
今回の問題では、生産表から「工場Yのレーン０では製品Aしか作らない」という制約があることを確認しました。

2. 問題の記述方法を考える

次に、それぞれの制約条件、目的関数について記述方法を考えていきます。
今回は、まず、制約条件をどのように記述するかを考えて、それに合わせて変数を定義する方法を決めます。それから、その定義した変数でどのように目的関数を記述するかを考えました。

2-1. 制約条件の記述の検討

まず、制約条件の記述方法について考えます。その際、変数をどのように定義すれば記述しやすいかも合わせて考えます。

1. 制約条件１（各工場での各製品の生産量が各工場からの各製品の輸送量以上になる）

生産量と輸送量をそれぞれ工場、製品毎に集計し、それぞれの集計結果を比較する。

• 変数定義時の考慮点：
  集計にはDataFrameのgroupbyメソッドが適している。
  よって、groupbyメソッドを使えるように、変数１（各工場、各レーンでの各製品の生産量）は、工場、製品のデータ列をもつDataFrameの一列として定義する。同じく、変数2（各工場から各商店への各製品の輸送量）も工場、商店のデータ列を持つDataFrameの一列として定義する。

2. 制約条件2（各工場での各レーンの各製品の生産量が各レーンの生産量上限以下になる）

変数１（各工場での各レーンの各製品の生産量）の上限値として設定する。

3. 制約条件3（各商店への各製品の輸送量（入荷量）が各商店での各製品の需要量以上になる）

輸送量を商店、製品ごとに集計し、その集計結果を需要テーブルの需要列と比較する。

• 変数定義時の考慮点：
  集計にはDataFrameのgroupbyメソッドが適している。よって、変数2（各工場から各商店への各製品の輸送量）は商店、製品のデータ列を持つDataFrameの一列として定義する。

4. その他に考慮すべき制約（工場Yのレーン０では製品Aしか作らない）

• 変数定義時の考慮点：
  変数１（各工場、各レーンでの各製品の生産量）は存在する工場、レーン、製品の組み合わせについてのみ（すなわち、生産表に合わせた形で製造不可能な工場Yのレーン0の製品Bの生産量は変数として作らないように）定義して満たすようにする。

2-2. 変数の定義方法の決定

次に、２−１.制約条件の記述の検討の各変数定義時の考慮点を踏まえて、具体的な変数の定義方法を決めます。

1. 変数1（各工場、各レーンでの各製品の生産量）

• 1、3の変数定義時の考慮点より、工場、レーン、製品のデータ列を持つDataFrameの一列として定義する。
• 2より、定義する際にLpVariableクラスのupBound引数に各工場での各レーンの各製品の生産量上限を渡す。
• 4より、行は生産表に合わせる。

DataFrame名：v_production

• columns=["工場","レーン","製品","生産量"]
• 生産量列の要素はLpVariable

2. 変数2（各工場から各商店への各製品の輸送量）

• 1の変数定義時の考慮点より、工場、商店、製品のデータ列を持つDataFrameの一列として定義する。

DataFrame名：v_transportation

• columns=["工場","商店","製品","輸送量"]
• 輸送量列の要素はLpVariable

2-3. 目的関数の記述方法の決定

最後に、2-2.変数の定義方法の決定で決めた変数を用いて、目的関数をどのように記述するかを決めます。

1. 製品の生産費：Σ(各レーンでの各製品の生産費)*（各レーンでの各製品の生産量）

変数1のデータ列を持つDataFrame（v_production）の行は生産表のDataFrameに対応させているので、変数1のデータ列と生産表のDataFrameの生産費のデータ列をlpDotで掛け合わせて算出する。

2. 各工場からの輸送費：Σ（各工場から各商店への輸送費）*（各工場からの製品の出荷量）

各工場から各商店への各製品の輸送量の変数の総和に対応する工場と商店間の輸送費（製品による違いはない）を掛けてlpSumで算出する。

この部分のコード：

# tb_trans_costは輸送表
for shop in shops:
	for factory in factories:
		prob += lpSum(tb_trans_cost[tb_trans_cost["商店"]==shop&tb_trans_cost["工場"]=factory, "輸送費"]*(v_transportation["輸送量"].groupby(["商店","工場"].sum())))

おわりに

実際には、上記の順でコードを考えたわけではなく、何度も書き直しました。まず変数を定義して、次に目的関数を書こうとして、いまいちだと思って変数を定義し直し、ようやく目的関数を書けたと思ったら、制約条件を書くのにこの変数定義じゃダメだ！となってまた変数を定義し直し…といった具合です。おかげで時間はかかりましたが、試行錯誤したからこそ、自分の中で実感を持ってこの順で考えるのが良い、という結論に至れたのかなと思います。さらに、参考にするためortoolpyのソースコードを解読することで、pythonの文法の理解を深めることもできましたし、最初はわからなかったortoolpy作者のコード作成意図が分かったときは単純に嬉しかったです。今後もこんな風にトライアンドエラーをしながら小さな分かった、できたの喜びを大切にしつつ、地道に学んでいきたいなと思いました。