CPLEX Optimization Studioのチュートリアルで最適化を体験してみる

はじめに

商用の最適化ソフトウェアであるIBM ILOG CPLEX Optimization Studioを触ってみました。CPLEXエンジンを使った記事は過去にもありましたが、このIDEを使った例が見当たらなかったので、記してみます。
この記事では、英語版しかない製品チュートリアルの内容を日本語化しつつ、できるだけ行間を補完することを目指します。CPLEXの完全なる初心者向けです。

やってみたチュートリアル

IBM ILOG CPLEX Optimization Studio 12.9 製品マニュアルのOrientation Guide > Completely new to CPLEX Optimization Studio?です。
使用したソフトウェアは、IBM ILOG CPLEX Optimization Studio 12.9.0 です。今回はMacOS版を使ってみました。

ビジネスの課題 (The business problem)

今回最適化したい問題です。実際のビジネス現場でもこのように言葉で表現されます。

• とある製造業。顧客に販売している製品が複数ある。

• 製品は、以下のいずれかの方法で調達する。

  1. 製造する。自社工場内で材料（リソース）を消費して生産する。
  2. 購入する。外部から購入して調達してくる。卸売業者みたいなイメージ。

• 1で製造したほうがコストは安いがリソースを消費する。2の購入はリソースを消費しないがコストは高い

• ビジネス目標は、顧客からの全注文(需要)に対応しつつ、全体的なコストを最小限に抑えること

よくありそうな製造業の課題をシンプルにしたもので、これを線形計画問題として解くという話です。ところどころIDEの使い方も解説しながら、チュートリアルは進んでいきます。

問題の定式化 (The mathematical representation)

上で述べたビジネスの課題を、数式で表現していく。チュートリアルでは既に数式が出来上がっているけど、ここは最適化スペシャリストが作り上げていく部分です。現実問題としては一番難しいところかも。

定式化された数式はこんな感じ（画像は製品マニュアルから引用）

大文字は定数、小文字は変数を表します。

データ(定数)	意味
$P$	製品の数（小文字$p$は$1$〜$P$の範囲のインデックス）
$R$	リソースの数（小文字$r$は$1$〜$R$の範囲のインデックス）
$C_{p,r}$	製品$p$の工場製造時のリソース$r$の消費量(Consumption)
$D_p$	製品$p$の需要量(Demand)
$INSIDECOST_p$	製品$p$の1単位の製造コスト(自社工場で製造）
$OUTSIDECOST_p$	製品$p$の1単位の購入コスト(外部からの購入)
$CAPA_r$	リソース$r$の上限(Capacity)
$in_p$	製造する製品$p$の数量（0以上)
$out_p$	購入する製品$p$の数量（0以上)

数式アレルギーの人に拒絶反応を示されそうですが、目をそらさずに眺めているとだんだんと理解できてくるはず。言っていることはこういうことです。

(1)は目的関数。minimizeは最小化したいという意味。全製品の調達総コスト = 自社内の製造コスト($INSIDECOST$ x $in$) + 外部からの購入コスト($OUTSIDECOST$ x $out$) の合計で、これを最小化したい。
$in_p$と$out_p$は、制御可能な変数（最適化対象となる変数）で、決定変数と呼ばれます。

subject to は制約条件を表す。製品は無限に調達できるわけではなく、限られたリソースで作らないと行けないし、顧客からの全注文にも応じないといけない。
制約条件としては、(2)(3)(4)の3つが定式化されている。

(2)はリソースの制約条件。製品を作るときのリソース消費量合計は、もともと保持していたリソースの最大容量を超えることはできない。資源は限りがあります。

(3)は需要の制約条件。製造数と外部からの購入量の合計は需要よりも大きい必要がある。顧客の注文（需要）にはすべて対応するよという話。

(4)は非負条件。製造数も購入数もマイナスではない、という基本的な条件。

コード化（OPLモデル定義）

CPLEX固有のOptimization Programming Language (OPL)という言語で、定式化した問題をコード化します。

チュートリアルで示されたコードを、部分毎に解説します。

{string} Products = ...; 
{string} Resources = ...; 
float Consumption[Products][Resources] = ...; 
float Capacity[Resources] = ...; 
float Demand[Products] = ...; 
float InsideCost[Products] = ...; 
float OutsideCost[Products] = ...; 

ここはデータ（定数）を定義しています。
3つのドット...は、別途データファイルとして定義された値を読み込むことを示します。（モデルとデータの分離）
stringは文字列、floatは実数の型で、{}は"Sets"と呼ばれる構造体（インデックスなし重複なし配列)、[]はArrayと呼ばれる構造体(インデックスあり配列)です。
Consumptionは、Arrayを2つつなげて2次元配列にしています。

dvar float+ Inside[Products]; 
dvar float+ Outside[Products]; 

決定変数(decision variables ; dvar)の定義です。
決定変数は最適化の中で調整可能な変数（最適化対象の変数）で、今回は製品毎の製造数Insideと購入数Outsideの2つです。
floatの後ろについている+は、0以上のプラスの値のみを取る型であり、これによって制約条件(4)非負条件を表現しています。

minimize 
  sum( p in Products ) 
    ( InsideCost[p] * Inside[p] + OutsideCost[p] * Outside[p] );

目的関数の定義です。
合計コストを最小化(minimize)したいという定義をしています。

subject to {
  forall( r in Resources )
    ctCapacity:
      sum( p in Products ) Consumption[p][r] * Inside[p] <= Capacity[r]; 

  forall(p in Products)
    ctDemand: 
      Inside[p] + Outside[p] >= Demand[p];
}

制約条件の定義です。
1つ目の制約条件名"ctCapacity"では、リソース制約条件(2)を記述しています。
2つ目の制約条件名"ctDemand"では、需要の制約条件(3)を記述しています。
"ct"は、英語の"制約 constraint"の略のようです。
なお、非負の制約条件(4)は、決定変数の定義内で、float+で表現されています。

上記のコードは、モデルファイルとして拡張子.modで保存することになります。

OPLは独特の言語で、慣れるまでに時間がかかりそうですが、CPLEXを使う上は避けては通れないので、リファレンスマニュアル等を見ながら少しずつ覚えていくしかなさそうです。

コード化（OPLデータ定義）

データ(定数）の定義は、モデル定義(拡張子mod)の中で直接記述しても良いですが、別ファイルとして記述することが可能です。データファイルと呼ばれます（拡張子.dat)。
データファイルとして別出しすることで、1つのモデルファイルで複数の定数セットに対応でき、条件を変えた複数の最適化パターンを試す時に便利です。

データファイル定義例その1 (ジュエリー)

リング(指輪）とイヤリングを作っている工場での例です。

Products = { "rings", "earrings" }; //index sets for 
Resources = { "gold", "diamonds" }; //products and resources 
Consumption = [ [3.0, 1.0], [2.0, 2.0] ]; 
Capacity = [ 130, 180 ]; 
Demand = [ 100, 150 ]; 
InsideCost = [ 250, 200 ]; 
OutsideCost = [ 260, 270 ];

定義された定数の意味は以下の通り。

製品$p$：リング、イヤリング
リソース$r$：金、ダイヤモンド
レシピ$C_{p,r}$：リング 金3,ダイヤモンド1／イヤリング 金2,ダイヤモンド2
リソース合計$CAPA_r$：金130、ダイヤモンド180
需要$D_p$：リング100、イヤリング150
製造コスト$INSIDECOST_p$：リング250ドル、イヤリング200ドル
購入コスト$OUTSIDECOST_p$：リング260ドル、イヤリング270ドル

データファイル定義例その2 (パスタ)

パスタ工場での例です。kluskiというのはWikipediaによると詰め物のない形状を指す、ポーランドの食べ物用語のようです。ググると丸いものや長細いもの、見たこと無いパスタでした。うちの息子が大好きなスパゲティは入ってませんね。

Products = {"kluski", "capellini", "fettuccine"}; 
Resources = {"flour", "eggs"}; 
Consumption = [ [0.5, 0.2], [0.4, 0.4], [0.3, 0.6] ]; 
Capacity = [ 20, 40 ]; 
Demand = [ 100, 200, 300 ]; 
InsideCost = [ 0.6, 0.8, 0.3 ]; 
OutsideCost = [ 0.8, 0.9, 0.4 ];

定義された定数の意味は以下の通り。

製品$p$：クルスキ、カペリーニ、フェットチーネ
リソース$r$：小麦粉、卵
レシピ$C_{p,r}$：クルスキ　小麦粉0.5、卵0.2／カペリーニ　小麦粉0.4、卵0.4／フェットチーネ　小麦粉0.3、卵0.6
リソース合計$CAPA_r$：小麦粉20、卵40
需要$D_p$：クルスキ100、カペリーニ200、フェットチーネ300
製造コスト$INSIDECOST_p$：クルスキ0.6、カペリーニ0.8、フェットチーネ0.3
購入コスト$OUTSIDECOST_p$：クルスキ0.8、カペリーニ0.9、フェットチーネ0.4

先に作ったモデルファイルで、この2つのデータファイルに対応可能です。このようにデータファイルを別にすることで、新たにペンネやリングイネを追加したい時に、データファイルだけ用意してモデルファイルは流用が可能、ということです。

ILOG CPLEX Optimization Studio (IDE) の操作方法

ここでチュートリアルでは、CPLEX Optimization Studioでの操作手順の解説が入ります。基本的な操作手順を理解します。

1.プロジェクトを作成（必須）

最初にプロジェクトを作成します。プロジェクトとは、モデルやデータが含まれる定義セットです。

2.モデルファイルを作成（必須）

Optimization Programming Language (OPL)でモデルを記述し、拡張子.modのファイルに保存します。

3.データファイルを作成（オプション）

OPLでデータ(定数)を記述し、拡張子.datのファイルに保存します。
2のモデルファイル内にデータを記述してもOKです（シンプルな方法）。

4.実行構成を作成 （必須）

実行構成とは最適化実行の対象となる定義で、モデルファイルとデータファイルが含まれます。
異なるデータファイルを使用する場合は、モデルファイルとデータファイルの組み合わせごとに実行構成を作成します。

5.実行

実行構成を右クリックして実行します。

その他のオプションとして、設定ファイル（拡張子.ops）を使用して各種定義を変更することも可能です。設定ファイルはプロジェクトまたは実行構成に追加します（詳細は省略）。

それでは、具体的にやっていきます。

CPLEX Optimization Studioに含まれるサンプルプロジェクト

CPLEX Optmization Studioには、多くのサンプルプロジェクト（モデルやデータファイル）が同梱されています。格納場所は、製品インストールフォルダ/opl/examples/oplです。

以降では、production というサンプルプロジェクトを使用して解説しています。このサンプルプロジェクトは、上で示したデータ例その2（パスタ）です。

サンプルプロジェクトproductionの実行

サンプルプロジェクトproductionを使って、プロジェクト・モデルファイル・データファイルの構造や、最適化を実行した結果を確認します。

######手順1.プロジェクトを開く
IBM ILOG CPLEX Optimization Studioを起動し、メニューからファイル > インポート > サンプル をクリックします。

IBM ILOG OPLの例を選択して、次へをクリックします。

検索窓に"production"と入力し、表示された"production"を選択した後、適切なコピー場所（プロジェクトを作成するフォルダ）を選択して、終了をクリックします。

######手順2.モデルファイル(mod)とデータファイル(dat)と実行構成を定義する
Productionプロジェクト作成後の状態です。既に定義された状態になっており、2つのモデルファイル(mod)と、3つのデータファイル(dat)が存在しています。モデルは最適化エンジンとして「CPLEX」のソルバーが呼び出されることを示しています。
実行構成は3つあり、各々異なるモデルファイルとデータファイルが紐付けられています。

実行構成 Baseic Configurationに登録されているモデルファイルやデータファイルをダブルクリックすると、右側の編集エリアに表示されます。各々、中身を確認します（上で述べたサンプルOPLコードが定義されている。データは例2のパスタのケース）

まっさらな状態から作る場合は、新規プロジェクトを作成し、モデルファイル(mod)やデータファイル(dat)をOPLで自分で記述し、実行構成を定義してモデルファイルやデータファイルを紐付けます。

######手順3.実行する
実行構成 Baseic Configurationを右クリック > これを実行 をクリックします。最適化処理が開始されるので、数秒待機します。

######手順4.最適化結果を確認する
CPLEXソルバーによる最適化計算の結果が、IDE画面の下部に表示されます。
画面左下には、使用したデータ(定数)、決定変数、制約条件の一覧があります。決定変数には、最適化結果も表示されています。
画面右下の"解 (solution)"タブを開くと、最適化結果が表示されます。

最適化結果（求められた決定変数）の意味は、このようになります。

需要Dと制約ctを満たす、最小コストとなる製造量Insideと購入量Outsideは、
製造量Inside クルスキ 40、カペリーニ 0、フェットチーネ 0
購入量Outside クルスキ 60、カペリーニ 200、フェットチーネ 300

カペリーニとフェットチーネは、自社工場で製造するよりも外部から購入した方が低コストということですね。

データファイル(dat)の定数を変えると、異なる最適化結果になるはずです。
試しに、フェットチーネの購入コストを0.4から0.5へ変更してみると、最適化結果は以下のようになりました。

Inside = [0 0 66.667];
Outside = [100 200 233.33];

フェットチーネの市場価格が上がったので、フェットチーネを優先的に自社工場で生産し、代わりにクルスキとカペリーニは外部調達するほうが良い、という結果にかわりました。

しかし相変わらず外部調達の比率が高いので、もう1つ実験。
上記の購入コストを元に戻した後、資源量Capacityを、Capacity = [ 20, 40 ];からCapacity = [ 150, 200 ];に増やします。
最適化結果はこう変わりました。

Inside = [100 50 266.67];
Outside = [0 150 33.333];

倉庫に小麦粉と卵が潤沢にあるので、コストの安い自社工場生産を増やしたほうがトータルコストが低くなるという結果にかわりました。

実際は在庫コスト等も考慮する必要があるでしょう。そうやって変数や定数を増やしていくと、次第に現実問題に近づいていきますね。

おまけ

製品マニュアルには、さらに詳しい機能や使い方を知るためのチュートリアルが複数あります。いつかこれらも試してみたいと思っています。
Becoming familiar with CPLEX Optimization Studio