Tokyo, Japan - 日本語
先日 https://community.alteryx.com/t5/Tokyo-Japan-日本語/分析系ツルの勉強はじめます/m-p/1171621 で宣言してから3週間たってしまいましたが
第一弾としまして、「最適化ツール」の勉強の覚え書きを共有します。
（といっても、内容はほぼ Tool Mastery | Optimization の逐語訳に近いのですが、ご容赦ください。）
最適化とは
Wikipedia:数理最適化 によれば、「ある条件に関して最もよい元を、利用可能な集合から選択すること」です。
これだけでは分かりにくいので、典型的な応用例である「ナップサック問題」を見てみましょう。
再び Wikipedia によれば、ナップサック問題とは以下のような問題です。
- １個あたりの価格と重さが決まった品物が複数種類ある。
- ある決まった重さまでしか品物を入れられないナップサックがある。
- ナップサックに品物を入れた品物の価格の合計を最大にするには、入れる品物の組み合わせをどのように選べばよいか？
最適化ツール
この種の「数理最適化問題」を解くためのAlteryxのツールが「最適化ツール」です。
最適化ツールが扱える問題には、以下の３種類があります。
- 線型プログラム(Linear Program)
- 混合整数プログラム(Mixed Integer Program, MIP)
- 二次計画法(Quadratic Program, QP)
ツール上の設定値では、以下のように選択します。
線形プログラム(LP)
変数と制約条件の値が連続値（実数）である場合に使います。
例：
- 植物の肥料に使う原料をどんな割合で調合すべきか（制約条件：植物の需要、原料の在庫、価格）
- ロンドン行のフライトの座席の料金をいくらにすべきか（制約条件：顧客の需要）
混合整数プログラム(MIP)
変数の一部が整数値に限定されている場合に使います。
例：
- 全ての航空便について搭乗員をアサインする問題（コストを最小化し、最低休息時間などの制約条件を満たす）
- 購入する原材料の数量を決める問題（コストと要求される生産量に基づき）
二次計画法(QP)
目的関数が二次関数であり制約条件が一次関数である場合に使います。
例：
- ポートフォリオ最適化問題
（期待収益を達成しつつリスクを最小化するリスク資産への投資比率を決定する問題）
これだけだと何のことか分からないので、Alteryx Community の参考ページを載せておきます。
Quadratic Programming with the Optimization Tool
最適化ツールの使い方
最適化ツールは入力アンカーが４個もあるため、一見 設定が難しそうに見えます。
設定について考える前に、まずは解決したい問題を整理しましょう。
- 制約条件はなにか？
- 何を「最適化」（最大化／最小化）したいのか？
- 結果のデータ型はなにか？
このような整理をすることで、前述のどの「問題タイプ」（線形, 混合整数, 二次計画法）を使うかが決まります。
これで設定に取り掛かる準備ができました。
問題設定
元のTool Masteryページの例では、同じ「混合整数プログラム」問題で使い方を見ていきます。
文脈は、
雑貨店の在庫の商品カテゴリー（ピーナツバター、ジャム、パン、牛乳）ごとに１つの製品を在庫に持ち
展示できる棚のスペースを超えない範囲で
雑貨店の利益を最大化する
という最適化問題です。
入力モード
「入力モード」の設定は以下の３種類があります。
- モデルを行列として指定
- モデルを手動で入力
- ファイルからモデルを指定する
モデルを行列として指定する方法
行列で入力するモードを選択する場合、入力アンカーはOとAは必須ですが、BとQは任意です。
Oアンカー
Oアンカーには以下のデータを設定します。
設定項目 | 意味 | 必須? | 説明 |
variables | 決定変数 | 必須 | 例題では商品名 |
coefficients | 計数 | 必須 | 最適化（最大化 or 最小化）するべきもの 例題では各商品の利益をあらわす |
lb / ub | 範囲 | 任意 | 各の決定変数(商品)がとることができる 下限値(lower bound)と上限値(upper bound) |
type | 変数型 | 任意 | 各の決定変数(商品)がとる事ができるデータ型 B (バイナリ型: binary) C (連続型: continuous) ⇒ デフォルト I (整数型: Integer) |
- 例題でのOアンカーの設定値
Record ID | variable | coefficient | lb | ub | Type |
1 | P1 | 3.7 | 0 | 1 | B |
2 | P2 | 5.2 | 0 | 1 | B |
3 | P3 | 6.1 | 0 | 1 | B |
4 | J1 | 9.3 | 0 | 1 | B |
5 | J2 | 9.6 | 0 | 1 | B |
6 | M1 | 4.8 | 0 | 1 | B |
7 | M2 | 7.2 | 0 | 1 | B |
8 | M3 | 9.1 | 0 | 1 | B |
9 | B1 | 2.6 | 0 | 1 | B |
10 | B2 | 5.4 | 0 | 1 | B |
- フィールド名マッピング機能
Version 11.0以降、Oアンカーに使うフィールド名を自由にマッピングする機能が提供されています。
これにより、正規のフィールド命名法とは異なるフィールド名を使う事ができる様になりました。
Aアンカー
Aアンカーには制約条件の表を入力します。
表の入力方法には3通りあります；
密行列、行の制約 (Dense Matrix, Constraints in Rows)
この方法では、入力する表の各行は制約条件に対応します。
Record ID | P1 | P2 | P3 | J1 | J2 | M1 | M2 | M3 | B1 | B2 | B3 | B4 |
1 | 12 | 16 | 18 | 21 | 24 | 18 | 21 | 28 | 1 | 15 | 18 | 24 |
2 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
3 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
4 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
5 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
例題では、1行目は各商品のサイズに対応し、
あとの行は各商品の商品タイプ（ピーナツバター、ジャム、パン、牛乳）をバイナリ型で表現します。
（0 = False, 1 = True)
密行列、行の変数 (Dense Matrix, Variables in Rows)
この方法では、決定変数は各行に対応し、制約条件は列に対応します。
Record | variable | Size | Jam | Milk | Peanut Butter | Sliced Bread |
1 | B1 | 1 | [null] | [null] | [null] | 1 |
2 | B2 | 15 | [null] | [null] | [null] | 1 |
3 | B3 | 18 | [null] | [null] | [null] | 1 |
4 | B4 | 24 | [null] | [null] | [null] | 1 |
5 | J1 | 21 | 1 | [null] | [null] | [null] |
6 | J2 | 24 | 1 | [null] | [null] | [null] |
7 | M1 | 18 | [null] | 1 | [null] | [null] |
8 | M2 | 21 | [null] | 1 | [null] | [null] |
9 | M3 | 28 | [null] | 1 | [null] | [null] |
10 | P1 | 12 | [null] | [null] | 1 | [null] |
11 | P2 | 16 | [null] | [null] | 1 | [null] |
12 | P3 | 18 | [null] | [null] | 1 | [null] |
１列目は各商品のサイズに対応し、あとの列は各商品が属する商品タイプを意味します。
"Null"はその商品が当該 商品タイプではないことを意味し、"1"はその商品が当該 商品タイプに属することを意味します。
スパース(SLAM)行列
スパース行列(Wikipedia:疎行列)は、前述の2つの行列の設定方法でNullか0がセットされている箇所が全て除外されています。
"SLAM"とは、スパース行列を正しい形式(SLAM)で与えられた時に、それを効率的に"翻訳"するR言語のパッケージのことです。
スパース行列での入力は、密行列に比べるとメモリをかなり節約できるため、大規模な制約条件を持つ最適化問題において有効です。
SLAM行列は3つのフィールド(i, j, v)から構成されます。
i | 行列の座標（行番号） |
j | 行列の座標（列番号） |
v | 行列の要素の値（非ゼロ） |
スパース行列に存在しない座標の値はゼロと推定します。
スパース行列は常に「行の制約」と解釈されます。
雑貨店の例題では、スパース行列の値は以下のようになります。
| 行 | 値 | 「密行列、行の制約」の値 |
| 1行目 | 1, 1, 12 | 1行目 1列目 の値は 12 |
| 2行目 | 2, 1, 1 | 2行目 1列目 の値は 1 |
この様にして全てのセルの値が表現されます（値がゼロのセルはスキップ）。
| i | j | v |
1 | 1 | 1 | 12 |
2 | 1 | 2 | 16 |
… | … | … | … |
23 | 5 | 11 | 1 |
24 | 5 | 12 | 1 |
スパース行列への変換方法
密行列からスパース行列への変換方法については添付ワークフローを参考にしてください。
Bアンカー
Bアンカーは変数の方向（制約条件の値に対する不等号・等号）を指定する為に使われます。
この情報がAアンカーでは提供されない場合に指定が必須となります。
雑貨店の例題がそのケースにあたります。
Aアンカーに方向("dir")と右辺の値("rhs")を指定する方法については、ヘルプを参照ください。
Bアンカーへ入力する列は
constraint | 制約条件 | 使用する名前はAアンカーの名前と一致させる |
dir | 方向（direction） |
|
rhs | 等式の右辺（right-hand side） | 数値 |
入力例
Record # | constraint | dir | Rhs |
1 | Size | <= | 80 |
2 | Peanut Butter | <= | 1 |
3 | Jam | <= | 1 |
4 | Milk | <= | 1 |
5 | Bread | <= | 1 |
この例では以下の制約条件を表現しています。
- 選んだ商品のサイズの合計は80以下
- 各商品カテゴリーから選んだ商品の数は1以下
Qアンカー
Qアンカーは、行列モードで二次計画法(QP)を指定する場合にだけ使われる入力アンカーです。
ここには、目的関数の二次関数部分を定義します。
密行列・スパース行列のどちらでも定義することができます。
密行列で指定する場合 | フィールド名はOアンカーで定義した決定変数の名前と一致させます。 |
スパース行列で指定する場合 | SLAM行列形式に従い、i, j, v の列名で記述します。 |
この入力方法（密行列）の入力例についてはこのDesingerのスレッドを参照ください。
モデルを手で個別に指定する方法
これは、目的関数と制約条件を直接 等式の形で、対話型のインターフェースで指定する方法です。
この指定方法では、入力アンカーは必要ありません。
詳細の指定方法については、Communityの記事 Optimization Tool: Entering a Model Manually に譲りますが、等式がどのようなものかを以下に示します。
Objectiveタブ
雑貨店の例題については、等式は以下のようになります。
3.7*P1 + 5.2*P2 + 6.1P3 + 9.3J1 + 9.6J2 + 4.8M1 + 7.2M2 + 9.1M3 + 2.6B1 + 5.4B2 + 5.8B3 + 6.9B4
各変数の計数は各商品の利益と、最大化(または最小化)すべき値です。
これを"Objective"タブに指定します。
Constraintsタブ
制約条件は複数の等式で"Constraints"タブで指定します。
例題の"サイズ"の制約条件については、等式は以下のようになります。
12 P1 + 16 P2 + 18 P3 + 21 J1 + 24 J2 + 18 M1 + 21 M2 + 28 M3 + 12 B1 + 15 B2 + 18 B3 +24 B4
各の変数とサイズをかけて足し合わせた値で、店舗のサイズが上限値となります。
「各商品タイプから1つの商品だけを選ぶ」という制約条件は以下の等式で指定します。
ピーナツバター | P1 + P2 + P3 == 1 |
ジャム | J1 + J2 == 1 |
牛乳 | M1 + M2 + M3 == 1 |
パン | B1 + B2 + B3 + B4 == 1 |
これらの等式は、各グループで選択された商品の数が１であることを示しています。
Bounds & Typesタブ
これらの選択肢をバイナリ型（選択するか、しないかのいずれか）に指定するには、"Bounds & Types"タブで指定します。
注意
R言語におけるソルバーは全ての変数を等式・不等式の左辺に置くルールとなっています。
つまり、等式
P1 + P2 + P3 == 1
は
P1 + P2 == 1 - P3
と同値ですが、変数"P3"が右辺にあることでツールは以下のエラーを返します。
error: R.exe exit code (3221225512) indicated an error
モデルをファイルから指定する方法
既にファイルに保存されたモデルがある場合、「ファイルからモデルを指定する」モードを指定して、これを最適化ツールにロードすることができます。
モデルファイルは以下の3形式のいずれかを使います。
この入力モードを選択した場合、入力アンカーや問題タイプを指定する必要はありませんが、
どのソルバーを使用するかは指定する必要があります。
参考
Alteryx Designerのサンプルワークフローに最適化ツールの各入力モードの例があります。
Help > Sample Workflows > Predictive tool samples > Prescriptive Analytics > 1 Optimization Model Input Modes
問題タイプを選択する
入力アンカーが設定できたら、次は問題タイプを指定します。
冒頭で説明したとおり、Alteryxの最適化ツールが扱える問題には、以下の３種類があります。
- 線型プログラム(Linear Program)
- 混合整数プログラム(Mixed Integer Program, MIP)
- 二次計画法(Quadratic Program, QP)
どの問題タイプが最適化は問題の設定段階で決まっているはずです。
ソルバーを選択する
問題タイプが設定出来たら、次はソルバーを選択できます。
線形プログラムか混合整数プログラムを扱っている場合、GlpkかSymphonyが選択できます。
二次計画法を扱っている場合、Quadprogが選択できます。
対象を最大化しますか？
最後に設定するのは「対象を最大化するか」の選択です。
これは対象を最小化するか最大化するかの二択のトグルスイッチです。
単位あたりのコストを扱う場合は、おそらくこのトグルはデフォルトのまま（最小化）でよいでしょう。
単位あたりの利益を扱う場合は、このトグルは最大化することになるでしょう。
出力
最適化ツールには3つの出力アンカーがあります。
Sアンカー
Sアンカーは最適化問題の解答を出力します。
Record # | name | value |
1 | Objective Value | 29 |
2 | B2 | 1 |
3 | J1 | 1 |
4 | M3 | 1 |
5 | P2 | 2 |
この例題では、最適化ツールは目的（利益）を最大化して29とするために P2, J1, M3, B2 を選択しました。
Dアンカー
Dアンカーは以下の3つのパイプ(|)で区切られたデータのテーブルを出力します。
Summary
Variables
Constraints
Record # | name | value |
1 | summary | Description|Value |
2 | summary | Objective Value|29 |
3 | summary | Problem Type|IP |
4 | summary | Objective|Maximize |
5 | summary | Number of Variables|12 |
6 | summary | Integer Variables (including Binary)|12 |
7 | summary | Binary Variables|12 |
8 | summary | Number of Constraints|5 |
9 | summary | Number of Nonzero Coefficients|24 |
10 | variables | Variable|Value|Coefficient|Type |
11 | variables | B2|1|5.4|B |
12 | variables | J1|1|9.3|B |
13 | variables | M3|1|0.1|B |
14 | variables | P2|1|5.2|B |
15 | constraints | Constraint|Value|Direction|RHS|Slack |
16 | constraints | Size|80|<=|80|0 |
17 | constraints | Peanut Butter|1|==|1|0 |
18 | constraints | Jam|1|==|1|0 |
19 | constraints | Milk|1|==|1|0 |
20 | Constraints | Bread|1|==|1|0 |
このデータはフィルタツールで[name]列の値ごとにテーブルを分けてから、列分割ツールをパイプ文字(|)を区切り文字にする事で、簡単にパーシングできます。
このデータは自分で最適化問題の解答のレポートやダッシュボードを作る際に便利です。
Iアンカー
Iアンカーは解答に関する対話型のダッシュボードを出力します。
このダッシュボードを操作するには、Informationアイコンと、各テーブルの上部の検索ボックスをクリックしてみてください。
その他のリソース
