Alteryx Predictive Master資格取得を目指すシリーズです。
Alteryxの処方的分析（Prescriptive）カテゴリをご存知でしょうか？
この中にある最適化（Optimization）ツールですが、これは数理最適化問題を解くことができます。Excelだとソルバーアドインに該当します。
数理最適化問題としては、「ナップサック問題」というものが有名です。いくつかサイズの異なる荷物があり、それぞれの金額が異なります。ナップサックの中になるべく大きな金額になるように荷物を詰める時、どれを選択するか、といった問題です。詰め方の全パターンを計算すれば確かにできますが、種類が増えると計算時間が天文学的に増加してしまいます。これを効率よく解くのが、数理最適化問題です。
さて、このブログはAlteryxのブログなので、今回はAlteryxの最適化ツールを見ていきたいと思います。
最適化（Optimization）ツール
このツールができることは、数理最適化問題を解くことがです。より詳しく見ていくと、
- 線形計画法（LP）
- 混合整数線形計画法（MILP）
- 二次計画法（QP）
を使って解くことが可能です。といわれても、馴染みがない方が多いと思いますので、正直なんのこっちゃ、だと思います。
そもそも数理最適化は、現実の問題を数式としてモデル化し、制約条件を満たしつつ、最適な値を求める、というものです。有名なものでは「ナップサック問題」、現実的によく使われているところでは、「電車のルート検索」「店員のシフト作成」「商品の配置最適化」なども該当します。
このツールは、現実の問題を数式に落とす能力が必要です。決して難しい数式ではないのですが、現実の問題を単純な数式に噛み砕くのはなかなか大変です。このあたり、数理最適化問題が理解しにくいポイントかと思います。
ちなみに、Designer ExpertやPredictive Masterなどの認定を受けるには、出題の範囲内に入っており、避けて通れません（まぁ、このツールを使う問題があれば捨てる、という受験上のテクニックもありますが）。
このツールを使いこなす一番の近道は、Designer付属のサンプルから解決したい問題に似たものをチョイスし、改造して使う、というのが近道かと思いますが、最初に動画を見て使い方を理解した方が良いかと思います（英語ではありますが・・・）。
サンプルは、ヘルプの「サンプルワークフロー」の「Predictive tool samples」の「Prescriptive Analytics」の中に５つのサンプルワークフローがあります。それぞれ簡単に紹介します。
- Optimization Model Input Modes
- Optimization Mixing Problem
- Optimization Fantasy Sports Lineup
- Optimization Workforce Scheduling
- Optimization Parse Detailed Output
１は、基本的な問題を解きますが、最適化ツールの解き方にいくつかオプションがあります（設定を、手動でセットする場合、データを取り込む場合、ファイルにする等のオプションがあります）。最適化ツールの使い方を紹介するようなワークフローです。
２は、線形計画法の典型的な問題の一つである「混合問題」を解くためのワークフローです。このワークフローでは、食品を作るのに、いくつかの材料と作るための食品の組成があり、各材料をどれくらい選択すれば、コストを最小、栄養を最大にできるか、という問題を解いています。
３は、野球のチームの選手のドラフトで指定された予算と決められた人数のポジションについて誰を指名するのが良いか最適な組み合わせを見つけるためのワークフローです。
４は、勤務のシフトを組むためのワークフローです。これは現実的な話に見えますが、他のユースケースに比べると結構構築の難易度は高いように思います。
５は、D出力の中身を変換してワークフロー内で使えるようにする方法を紹介しているものになります。
具体的な問題を考えてみます。例えば、車でドライブに行くのに、車についているナビがUSBメモリにmp3ファイルを入れて再生できるものとします。手元にあるUSBメモリは1Gなのですが、この中にお気に入りの曲を容量ギリギリまで詰め込みたいとします。すべての楽曲には点数をつけていますが、USBメモリギリギリいっぱいに入れつつ、点数を最大化するのにはどの曲を入れればよいか？
というのは非常にわかりやすい最適化ツールを使う例かと思います。
以下、設定を解説していきますが、サンプルワークフロー「_1_Optimization_Model_Input_Modes.yxmd」に従って説明していきます。
1 Optimization Model Input Modes
ヘルプメニューの「サンプルワークフロー」－「Predictive tool samples」－「Prescriptive Analytics」にあるワークフロー「1 Optimization Model Input Modes」では、以下のような例を扱っています。
問題：食料品店の棚に並べたい４つの商品カテゴリーにおいて、どの商品を置くべきか？
条件：
- 棚に並べる商品の利益を最大化したい（それぞれの商品の利益が与えられています）
- 棚のサイズに納める必要があります。サイズは８０
- それぞれのカテゴリから最低一つは選択する必要があります。カテゴリは、Peanut Butter、Jam、Milk、Sliced Breadの４つ。
これに対して、以下のようなデータが与えられています。
このデータであれば以下のような条件を考えられます。
目的（Objective）
各プロダクトと利益（cost）をかけ合わせたものを最大化する
制約式
- 各プロダクトとサイズをかけ合わせたものの合計が80以下
P1*12+P2*16+P3*18+J1*21+J2*24+M1*18+M2*21+M3*28+B1*1+B2*15+B3*18+B4*24 <= 80- 各プロダクトのカテゴリーに最低一つ必要
P1*1+P2*1+P3*1 <= 1
J1*1+J2*1 <= 1
M1*1+M2*1+M3*1 <= 1
B1*1+B2*1+B3*1+B4*1 <= 1設定
設定は、「入力モード」によって変わります。
- モデルを行列から指定（Specify the model as matrices）
- モデルを手動で入力（Enter the model manually）
- ファイルからモデルを指定する（Specify the model from a file）
それぞれの方法において、使用するアンカーも異なります。そのため、すべてのアンカーはオプション（白いアンカー）になっています。基本的に「モデルを行列から指定」の場合のみに入力アンカーは使われます
入力アンカーO
目的（Objective）に関わる部分と、下限値、上限値などの各変数の定義を入力します。
具体的には、変数名（variable）、係数（coefficient）、下限値（lb）、上限値（ub）、データ型（type）を入力します。
Objectiveとしては、variable×coefficientの合計値となります。これを最大とするか、最小とするか、というのを計算し、それぞれの変数の数量を出す、というのが最適化ツールの基本的な動きです。
データ型（type）は、以下の３つのいずれか適切なものを入力します。
C：連続型。小数点を含む数値が入ります。
I：整数型。整数値が入ります。イメージ的には個数、というのが近いと思います。
B：バイナリ型。0か1となります。つまり、あるかないか、というイメージです。
上限値（ub）に制約がない場合「Inf」という文字列を入れることが可能です。
この例では、置くか置かないかなので、データ型としてはBとしています。また、Bの場合は、lbは0、ubは1となります。
入力アンカーA
入力アンカーA、Bはセットで用います。制約式の左辺（Aアンカー）と右辺（Bアンカー）をそれぞれ入力します。
入力アンカーAの制約モードを「密行列、行の制約」とした場合は以下のようなデータを入力します。
上記の入力は、以下の制約式のうち赤い部分となります。
P1*12+P2*16+P3*18+J1*21+J2*24+M1*18+M2*21+M3*28+B1*1+B2*15+B3*18+B4*24 <= 80
P1*1+P2*1+P3*1 <= 1
J1*1+J2*1 <= 1
M1*1+M2*1+M3*1 <= 1
B1*1+B2*1+B3*1+B4*1 <= 1つまり、係数（赤色）と変数（水色）に分解し表にしています。
P1*12+P2*16+P3*18+J1*21+J2*24+M1*18+M2*21+M3*28+B1*1+B2*15+B3*18+B4*24 <= 80
P1*1+P2*1+P3*1 <= 1
J1*1+J2*1 <= 1
M1*1+M2*1+M3*1 <= 1
B1*1+B2*1+B3*1+B4*1 <= 1入力アンカーAの制約モードを「密行列、行の変数」とした場合は以下のようなデータを入力します。
これは、「密行列、行の制約」の表現の仕方を縦横で入れ替えた形となっています。本質的には変わりませんが、入力アンカーB側の式名称（constraint）と各フィールド名を一致させる必要があります。
入力アンカーB
入力アンカーBは、制約式の右辺と条件を記載します。dirは「==」「<=」「>=」のいずれかになります。必ず「=」が入っている必要があります（つまり、以上、以下、イコールしか指定できません）。
式名称（constraint）、dir（方向）、rhs（右辺）の３つを記載します。入力アンカーで見ていた制約式から、以下のように赤い部分をdir（方向）、水色部分はrhs（右辺）に記載します。
P1*12+P2*16+P3*18+J1*21+J2*24+M1*18+M2*21+M3*28+B1*1+B2*15+B3*18+B4*24 <= 80
P1*1+P2*1+P3*1 <= 1
J1*1+J2*1 <= 1
M1*1+M2*1+M3*1 <= 1
B1*1+B2*1+B3*1+B4*1 <= 1式名称（constraint）は、入力アンカーAの制約モードを選択のオプションにて「密行列、行の変数」を指定した場合は、入力アンカーAの項目名に対応させます。「密行列、行の制約」にした場合は単にレポートを見やすくさせるためだけのものです。
入力アンカーQ
問題タイプが二次計画法の時のみ入力します。実はサンプルにも入力例がないという困ったちゃんです。ツールマスタリーでも、Designerのディスカッションページを参照するように指示があります。
例えば、以下のようなデータとなるようです。
モデルを行列として指定（Specify the model as matrices）
入力が動的に変化する場合は、こちらの方法を取ってください。ただし、入力データのフィールド名が完全に一致してないと動作しないため、癖が強いです（例えば、フィールド名の大文字・小文字が違ってもNGです）。これを緩和するには、「入力アンカーOのフィールドマッピングを表示」のチェックを入れ、フィールドをマッピングすることをおすすめします。
問題タイプを選択（Select problem type）
問題タイプは以下３つから選択します。
- 線形プログラム
- 混合整数プログラム
- 二次計画法
この問題タイプに応じて選択できるソルバーが決まります。
ソルバーを選択（Select solver）
ソルバーは以下の３つから選択できますが、Glpk、Symphonyが選択できるのは線形プログラム、混合整数プログラムの場合で、二次計画法を選択すると、Quadprogしか選択できません。
- Glpk
- Symphony
- QuadProg
Glpkは、「GLPK(Gnu Linear Programming Kit)」で、線形計画問題（LP）や混合整数計画問題（MIP）を解くソルバーです。Symphonyは、混合整数計画問題（MIP）を解くソルバーです。
対象を最大化しますか（Maximize Objective?）
Objectiveの計算結果が最大のものを必要とする場合、チェックを入れます。そうではない場合はチェックをはずします。
入力アンカーA制約モードを選択（Select constraint mode for Input Anchor A）
入力のアンカーAに入力されているものが、どのフォーマットに対応しているか、というのを選択します。
- 密行列、行の制約（Dense matrix, constraints in rows）
- 密行列、行の変数（Dense matrix, variables in rows）
- スパース（SLAM）行列（Sparse(SLAM) matrix）
上２つは、行方向（縦方向）が制約条件なのか変数なのかで選択します。
最後のスパース行列は「密行列、行の制約」を行番号、列番号を用いて縦持ちにしたものですが、Nullと0を抜いてデータを圧縮しています。Tool Mastery | Optimizationに付属のサンプルワークフローでやり方を確認できます。
モデルを手動で入力（Enter the model manually）
一番設定がわかりやすく簡単なのがこのモードです。ただし、変数などが動的に変わる場合は、「モデルを行列から指定」で行ったほうが良いです。
この方法の利点は、とにかく簡単なことです。Objective、Constraints、Bounds & Typeを埋めていくだけです。教育用のビデオでは、この方法で解説されています。
設定方法としては、最初にVariable Listを入力します。その後「Objective」「Constraints」「Bounds & Types」という3つのタブを設定します。入力アンカーを使うより直感的に設定が可能です。
上の設定ではObjectiveタブの設定を確認できますので、残りのタブをお見せします。
Constraintsタブ：
数式を本来の形で書くことができるので、他のモードより楽です。
Bound & Typesタブ：
こちらは、変数が多いと書くのが面倒ですね・・・。
ファイルからモデルを指定する（Specify the model from a file）
特定の書式で記載されたファイルを入力として設定を行います。使用できる形式は、CPLEX_LP、MPS_Free、MathProgとされています。サンプルワークフローでは、CPLEX_LPフォーマットが使われています。
例えば、CPLEX_LPフォーマットは以下のような形となります。
Maximize
Profit: 3.7 P1 + 5.2 P2 + 6.1 P3 + 9.3 J1 + 9.6 J2 + 4.8 M1 + 7.2 M2 + 9.1 M3
+ 2.6 B1 + 5.4 B2 + 5.8 B3 + 6.9 B4
Subject To
Size: 12 P1 + 16 P2 + 18 P3 + 21 J1 + 24 J2 + 18 M1 + 21 M2 + 28 M3
+ 12 B1 + 15 B2 + 18 B3 + 24 B4 <= 80
Peanut: P1 + P2 + P3 <= 1
Jam: J1 + J2 <= 1
Milk: M1 + M2 + M3 <= 1
Bread: B1 + B2 + B3 + B4 <= 1
Binaries
P1 P2 P3 J1 J2 M1 M2 M3 B1 B2 B3 B4
End結果を見る
出力アンカーは、3つありますが、サマリーが最終的な結果となります。
出力アンカーS（サマリー出力）
結果が端的に出てきます。
目的の値、というのが、今回のサンプルであれば得られる「利益」です。
その他、２行目以降は、0以外の値が入っている変数が出力されます。つまり、今回のサンプルであれば、P2、J1、M3、B2を選択しましょう、ということになります。
出力アンカーD（詳細出力）
ｓ出力は端的な結果のみなので、合ってるかどうかわかりにくいです。D出力の制約式がどのように満たされているか確認することをおすすめします。これを読み取りやすい形に変換するためのワークフローがサンプルワークフローの５として用意されています。
出力アンカーI（動的レポート出力）
D出力を確認しなくても、こちらの動的レポートの方が見やすいかもしれません。
サンプル問題
サンプルの問題も案外少ないのがこの最適化ツールの難しいところです。現時点では、ウィークリーチャレンジに２個あるのみとなります。
#52は英語版のWeekly Challengeのみの問題ですが、ナップサック問題を解くチャレンジです。繰り返しマクロや位置最適化マクロでも解けるのですが、最適化ツールに最も適した問題です。ただし、ソリューションファイルでは最適化ツールは使われていないので、他の皆さんの回答例を見てください。私の回答例はこちらです。
参考
最適化ツールのトレーニングビデオです。５０分くらいありますが、一通り具体的な問題を解きながら説明してくれるため、非常に内容としては充実していると思います（英語ではありますが・・・）。トレーニング用のワークフローもダウンロードできます。ちなみに、頭の７分くらいは聞かなくても大丈夫です。ちなみに、通常の記事のバージョンもあります。「Optimization Tool: Entering a Model Manually」。ユースケースとしては、サンプルワークフローの２に近いイメージです。
「Summer Camp: Flex Your Prescriptive Optimization Muscles」もほぼ同じ題材のビデオとなっています。こちらは2020年のビデオで、少し新しいですが、ビデオの後半はオーディオの問題があります・・・。
ACEによるブログ。最適化ツールの概要、サンプルワークフローを簡単に読み解いています。英語ですが右クリックで翻訳すれば読めると思います。
ツールマスタリーです。一通り細かく書かれています。
ACEによるブログ。ドット絵をレゴで構築するのに、１ドット＝１レゴではなく、様々なサイズのレゴへの置き換えを最適化ツールを使って行っています。惜しいのは、Galleryのリンクが切れているため、どのようなワークフローで実現できるのかわからない点です。ただ、このようなものができる、というのがポイントかと思います。
「Python実践データ分析100本ノック」に掲載されていた輸送最適化問題をAlteryxで解いてみました。
まとめ
- 最適化ツールは、数理最適化問題を解くことができるツールです
- 現実の問題をいかに制約式に落とし込めるかがポイントです
- 「モデルを手動で入力」の設定が簡単ですが、変数が多い場合、動的に式を構築したい場合は、「モデルを行列として指定」の利用を検討してください。
- サンプルワークフローの追加の解説はこちらです。
- このツール馴染みがなさすぎるのと敷居を高く感じるので、正直Predictive Master資格の取得では最後の大ボス的な立ち位置です・・・が覚えれば意外といけますよ！（Designer Expertでも出題されます）。
コメント