Alteryx Weekly Challenge #52を例にしたOptimizationツールの解説

「カスタマーストーリー」を支えるツール特集

#ビジネス・アナリティクス

#Alteryx

じょんすみす

2019.01.11

この記事は公開されてから1年以上経過しています。情報が古い可能性がありますので、ご注意ください。

こんにちは、小澤です。

本記事は、Weekly Challengeに挑戦するシリーズではないのですが、題材としてWeekly Challengeの問題を扱っています。

PrescriptiveにあるOptimizationツールを使ってどのようなことができるのかを見ていくのがメインとなっていますので、問題の解答ズバリそのものは期待しないでください。

Weekly Challenge #52とナップサック問題

この問題は、タイトルが「Solving the Knapsack Problem」となっている通りナップサック問題というものを解くことになります。

最初にこのナップサック問題がどのようなものなのかを解説します。

Wikipediaではナップサック問題について以下のように説明されています。

ナップサック問題（ナップサックもんだい、Knapsack problem）は、計算複雑性理論における計算の難しさの議論の対象となる問題の一つで、「容量 C のナップサックが一つと、n 種類の品物（各々、価値 pi, 容積 ci）が与えられたとき、ナップサックの容量 C を超えない範囲でいくつかの品物をナップサックに詰め、ナップサックに入れた品物の価値の和を最大化するにはどの品物を選べばよいか」という整数計画問題である。同じ種類の品物を1つまでしか入れられない場合（xi ∈ {0, 1}）や、同じ品物をいくつでも入れてよい場合（xi ∈ 0以上の整数）など、いくつかのバリエーションが存在する。

ナップサック問題 - Wikipediaより

さて、これだけだと数式的なものとか出てきてつらいですね。。

簡単に解説すると、何種類かの品物があります。それぞれの商品は異なる価値(金額など)と重さ(または大きさ)が設定されています。ナップサックの中にこれらを詰め込みたいのですが、ナップサックは大きさが決まっており全部の品物を入れることはできません。そこで、

ナップサックに入れた品物の価値の合計がなるべく大きくなるようにする
ただし、重さがナップサックの許容量は超えないようにする

という条件で、「何を入れればいいか」を求める問題となります。

具体例を出したほうがわかりやすいかと思います。 Weekly Challenge #52では品物の価値と重さがそれぞれ以下のように設定されています。

品物	金額($)	重さ(kg)
品物1	4	12
品物2	1	2
品物3	2	2
品物4	1	1
品物5	10	4

これらを合計で15kgまで詰め込めるナップサックに入れるわけです。

金額の合計が最も多くなるようにナップサックに品物を入れる
重さの合計は15kg以下となるようにする

ナップサック問題は、特定の品物を入れる/入れないのみに限定したものと、同じ品物を複数入れていいものがありますが、今回は前者を扱います。

Optimizationツールで実際に解いてみる

ナップサック問題を解くのにOptimizationツールは"まさにそういうことをするためのツール"という代物なのですが、残念ながら、この問題が出題された当時まだ存在しないツールでした。そこため、解答例でも使用されていません。

今回は、Optimizationツールの使い方の紹介がメインとなるため、Weekly Challengeそのものを解くわけではありませんが、簡単にWeekly Challengeがどのような問題なのか確認しておきましょう。

この問題では2つの出力が求められています。

入れていい品物の数を1, 2, 3, 4個に限定した時のそれぞれの合計金額
15kg以下になる品物数・合計金額の全ての組み合わせ

ですが、今回は流れを簡単にするため、入れていい数を限定せずナップサック問題を解くことのみをしてみたいと思います。

ワークフローの全体像は以下のようになります。

入力データは以下のようになっています。

lat, long, CentroidはLocation Optimizer Macroというものを使う人向けのダミー変数なので今回は使用しません。

"品物名"に対応する列が存在しないので、RecordIDを振ることで疑似的に品物名としているのが1つ目のRecord IDツールの役割となっています。

その後、Optimizationツールの入力に必要なデータを生成するために

品物名と金額のみのデータ
品物名と重さのみのデータ

に分けています。また、Optimizationツールでは一部入力の列名にも指定があるため、以下のようにしています。

品物名 : variable
金額 : coefficient

重さに関してはkgをそのまま利用しています。

金額側のSelectツールにつながったFormulaツールでは、以下の設定をしています。

これによって以下のようなデータが生成されます。

この"B"が何を意味するのかは後程解説しますが、列名は必ず「type」であることも必須です。

一番下にあるText Inputツールでは、以下のようなデータを作成してます。

こちらは、品物のデータに含まれない"重さが15kg以下になること"という条件の部分を記載したものになります。 dirで等号や不等号など条件になるもの、rhsでその値を設定します。これらは列名もこの値である必要があります。

これらを上から順にOptimizationツールのQ以外に接続します。

一番上の「O」には、最大化(あるいは最小化)したいものを数式であらわしたものを入れます。今回の場合"ナップサックに入っている品物の合計金額"を最大化したいので、variable列に品物名、coefficient列にそれぞれの金額としたデータを渡しています。ここで3つ目の列であるtype列が機能します。金額の最大化の数式としては、

[latex] 品物1の金額 * 個数 + 品物2の金額 * 個数 + 品物3の金額 * 個数 + 品物4の金額 * 個数 + 品物5の金額 * 個数 [/latex]

となるわけですが、type列の値を"B"とすることで、その品物の個数を0か1のみに限定しています。こうすることで、0なら入れない、1なら入れるという状態が出来上がります。

2つ目の「A」には制約条件となる項目を追加します。今回はナップサックに入れることのできる重さが決まっているいるので、それぞれの品物の重さを渡しているわけです。これは以下のような式を定義している状態です。

[latex] 品物1の重さ * 個数 + 品物2の重さ * 個数 + 品物3の重さ * 個数 + 品物4の重さ * 個数 + 品物5の重さ * 個数 [/latex]

3つ目の「B」では、制約の式が満たさなければならない値を指定しています。「dir」には"<="、「rhs」には15を指定しているので、先ほどの「A」の式の計算結果が15kg以下であることを指定しています。

これら3つによって、

金額の合計が最も多くなるようにナップサックに品物を入れる
重さの合計は15kg以下となるようにする

という条件をOptimizationツールに渡すことができましたので、これでこの問題が解ける状態になりました。

ツールの設定は、以下のようになっています。

ほぼほぼ初期設定のままですが、金額を"最大化"したいので、「Maximize Objective?」はONの状態になっていることは必ずご確認ください。

実行すると、「S」の出力から以下のような結果が得られます。

これは「品物2-5をそれぞれ1つずつ」というのがこの問題の答えということを示しています。なお、先頭行のObjective Valueはナップサックに入れた商品の合計金額になっています。

これで必要な結果が得られたわけですが、後続の処理では簡単な集計を行っています。

Objective Valueで出力されている値をSampleツールで取り除いたあと、Joinツールで元データと結合しています。

これに対して、元データの金額・重さと出力のvalue(個数)を掛けた値を計算して、Summarizeツールで集計することで、金額と重さ合計および品物の数を計算しています。

金額に関してはObjective Valueと一致していることも確認できます。

また、今回は各品物を入れる/入れないでの最適化となっていますが、「同じ品物を複数個入れてもいい」という条件であれば、type列の値を"B"ではなく"I"にすることで任意の数の整数とすることができます。

Optimizationツールではtype列の値は必須ではありませんが、指定がない場合、取りうる値に制限がない状態(typeにCを指定しているのと同じ状態)となります。この状態だと、品物5が3.75個のような、小数点を含む値となってしまいこの問題に対しては望ましくありません。解きたい問題によっては小数点を含むほうがいい場合もありますし、とりうる値の範囲は適切に設定するようにしましょう。