(57)【要約】【課題】決定最適化に対するスケーラブルなアルゴリズムのための方法および装置を提供すること。【解決手段】最適化問題を解くための反復的アプローチが、提供される。本発明は、以下の4つの基本的動作の反復を提供する；セグメントを決定する、セグメントを平衡させる、セグメントを拡張する、およびセグメント最適化を解く。方法および装置は、解決動作中に、Dash OptimizationによるDash Optimization Xpressなどの、任意の既製の線形計画法(LP)ソルバを使用することができる。ソルバに供給された問題のサイズは、制限があり、かつ全部の問題のサイズと比較して相対的に小さいままである。したがって、アルゴリズムは、数オーダ−大きな問題を解くことができる。本発明の1つの実施例において、サンプリングおよびセグメント化法は、問題がアカウントレベルで解かれるまで、取り除かれる。上記の場合、アルゴリズム内で呼び出されるソルバが、最適な解を戻す場合、真の大域的解を達成することに対する疑いが、取り除かれるので、解は、さらに低コストで生成され、かつ最良のリターンは、達成される。【選択図】図３【特許請求の範囲】
【請求項１】
決定最適化問題に対する解を決定するためのコンピュータ実施の反復的方法であって、
行パーティションを決定するステップと；
当該決定された行パーティションを平衡させるステップと；
当該平衡させられた行パーティションを拡張するステップと；
解を出力するために当該拡張された行パーティションを解くステップとを有し、
当該解が、現在の解より良い場合、前記現在の解を当該解と取り替え、かつ行パーティションを決定する当該ステップで方法を繰り返す、そうでなければ、当該平衡させられた行パーティションを拡張する当該ステップで方法を繰り返す、方法。
【請求項２】
行パーティションを決定する当該ステップが：
オリジナルの線形計画問題(OLP)の最初の解を計算するステップと、当該最初の解を現在の解として設定するステップと、行パーティションを決定するために、当該現在の解を使用するステップとをさらに有し；
当該拡張するステップが：
当該平衡させられた行パーティション間からの任意のセグメントが、拡張されない非シングルトンでないかを決定するステップであって、当該ステップが：
当該平衡させられた行パーティション間からの任意のセグメントが、拡張されない非シングルトンでない場合、方法を終了するステップと；
そうでなければ、当該平衡させられた行パーティション間からの任意のセグメントが、拡張されない非シングルトンである場合、新しい行パーティションを生成するために、当該拡張されない非シングルトンセグメントを拡張するステップとをさらに有するステップと；
当該拡張されない非シングルトンセグメントを拡張することに応じて、当該新しい行パーティションを解くためにソルバを適用するステップと；
当該解かれた行パーティションを使用して、より良い目的関数値が利用可能であるかを決定するステップとをさらに有し：
より良い目的関数値が利用可能でない場合、当該平衡させられた行パーティション間からの任意のセグメントが、拡張されない非シングルトンでないかを決定する当該ステップへ進み；かつ
より良い目的関数値が利用可能である場合、当該解かれた行パーティションを使用することにより当該現在の解をアップデートし、かつ行パーティションを決定するために当該現在の解を使用する当該ステップへ進む、
請求項1に記載のコンピュータ実施の反復的方法。
【請求項３】
当該最初の解が、行パーティションを解くことにより得られるオリジナルの線形計画問題 (OLP)の基底解 B であり、 かつ当該解くステップが、基底解を戻すソルバを使用する
請求項1に記載のコンピュータ実施の反復的方法。
【請求項４】
当該行パーティションを決定するステップが：
オリジナルの線形計画問題 (OLP)の基底解Bに基づいた、行パーティション、Mおよび前記行パーティションMに基づいた前記線形計画問題、OLP[M]の基底解B*を、MおよびBを使用して生成するステップを
さらに有する請求項1に記載のコンピュータ実施の反復的方法。
【請求項５】
当該行パーティションを平衡させる当該ステップが：
依然としてMにより表わされている新しい行パーティションを生成するためにMを再平衡させるステップと；
[当該新しい行パーティションMの]OLPの基底解を当該B*から計算するために、当該新しい行パーティション、Mを使用して基底平衡させるステップとを
さらに有する請求項4に記載のコンピュータ実施の反復的方法。
【請求項６】
Mの全ての非シングルトンセグメントが、使用可能なまたは拡張されないとしてマークされる
請求項5に記載のコンピュータ実施の反復的方法。
【請求項７】
当該方法を終了するステップが、Mを戻すステップと、B*およびMを使用して、B*を構成要素に分解することにより前記オリジナルの線形計画問題(OLP)の解を戻すステップとを
有する請求項6に記載のコンピュータ実施の反復的方法。
【請求項８】
当該拡張されない非シングルトンセグメントを拡張するステップが、使用可能なセグメント、Mqを選択し、Mqを使用不能な(または拡張された)としてマークするステップと、MからMqを取り去り、かつMqの各要素をMにセグメントとして加えることによりMqを拡張するステップと、前記新しく生成された行パーティションをWに格納するステップとを
有する請求項7に記載のコンピュータ実施の反復的方法。
【請求項９】
当該拡張された行パーティションWを解くためにソルバを適用するステップが：
W内のシングルトンである全ての行レコードの集合、OLP[M]をS(M, Mq)に投影することにより得られるOLP[M, Mq, B*]を解くステップと；
OLP[M, Mq, B*]の前記戻された解およびB*を使用して、OLP[W]の基底解、B=Basis(W, OLP[M, Mq, B*])を計算するステップとを
さらに有する請求項8に記載のコンピュータ実施の反復的方法。
【請求項１０】
より良い目的関数値が利用可能であるかを決定するステップが：
BestObj<Obj(B)かを決定するステップをさらに有し、Obj(B)が、請求項9の当該基底解Bを使用して計算される前記目的値を格納するためのダブルであり、かつ今までに計算された前記最良の目的値、BestObjがダブルである、
請求項8に記載のコンピュータ実施の反復的方法。
【請求項１１】
当該解くステップが、基底最適な解を戻す場合、当該方法は、オリジナルの線形計画問題の最適な解を戻す
請求項1に記載のコンピュータ実施の反復的方法。
【請求項１２】
決定最適化問題に対する解を反復的に決定するためのコンピュータネットワーク上の装置であって：
行パーティションを決定する手段と；
当該決定された行パーティションを平衡させる手段と；
当該平衡させられた行パーティションを拡張する手段と；
解を出力するために当該拡張された行パーティションを解く手段とを有し；
当該解が、現在の解よりより良い場合、前記現在の解を当該解と取り替え、かつ行パーティションを決定する当該手段からスタートすることを繰り返すための手段を有し、そうでなければ、当該平衡させられた行パーティションを拡張する手段からスタートを繰り返すための手段を有する、装置。
【請求項１３】
行パーティションを決定するための当該手段が：
オリジナルの線形計画問題(OLP)の最初の解を計算する手段と、当該最初の解を現在の解として設定する手段と、行パーティションを決定するために、当該現在の解を使用する手段とをさらに有し；
拡張するための当該手段が：
当該平衡させられた行パーティション間からの任意のセグメントが、拡張されない非シングルトンでないかを決定するためのステップであって、当該ステップが：
当該平衡させられた行パーティション間からの任意のセグメントが、拡張されない非シングルトンでない場合、方法を終了するステップと；
そうでなければ、当該平衡させられた行パーティション間からの任意のセグメントが、拡張されない非シングルトンである場合、新しい行パーティションを生成するために、当該拡張されない非シングルトンセグメントを拡張するステップとをさらに有し；
当該拡張されない非シングルトンセグメントを拡張するための手段に応じて、当該新しい行パーティションを解くために当該ソルバを適用するソルバを提供する手段と；
当該解かれた行パーティションを使用して、より良い目的関数値が利用可能であるかを決定する手段とをさらに有し：
より良い目的関数値が利用可能でない場合、当該平衡させられた行パーティション間からの任意のセグメントが、拡張されない非シングルトンでないかを決定する当該ステップに進み；かつ
より良い目的関数値が利用可能である場合、当該解かれた行パーティションを使用することにより当該現在の解をアップデートし、かつ行パーティションを決定するために当該現在の解を使用する当該ステップへ進む、
請求項12に記載のコンピュータネットワーク上の装置。
【請求項１４】
当該最初の解が、行パーティションを解くことにより得られるオリジナルの線形計画問題(OLP)の基底解Bであり、かつ当該解くステップが、基底解を戻すソルバを使用する
請求項12に記載のコンピュータネットワーク上の装置。
【請求項１５】
行パーティションを決定するための当該手段が：
オリジナルの線形計画問題(OLP)の基底解Bに基づいた、行パーティション、M、および前記行パーティションMに基づいた前記線形計画問題OLP[M]の基底解B*を、MおよびBを使用して生成する手段を
さらに有する請求項12に記載のコンピュータネットワーク上の装置。
【請求項１６】
当該行パーティションを平衡させる当該手段が：
なおMにより表わされる新しい行パーティションを生成するためにMを再平衡させる手段と；
[当該新しい行パーティションMの]OLPの基底解を当該B*から計算するために、当該新しい行パーティション、Mを使用して基底平衡させる手段とを、さらに有する請求項15に記載のコンピュータネットワーク上の装置。
【請求項１７】
Mの全ての非シングルトンセグメントが、使用可能なまたは拡張されないとしてマークされる
請求項16に記載のコンピュータネットワーク上の装置。
【請求項１８】
当該方法を終了する手段が、Mを戻す手段と、B*およびMを使用して、B*を構成要素に分解することにより、前記オリジナルの線形計画問題(OLP)の解を戻す手段とを
有する請求項17に記載のコンピュータネットワーク上の装置。
【請求項１９】
当該拡張されない非シングルトンセグメントを拡張する手段が、使用可能なセグメント、Mqを選択し、Mqを使用不能な(または拡張された)としてマークする手段と、MからMqを取り去り、かつMqの各要素をMにセグメントとして加えることにより、Mqを拡張する手段と、前記新しく生成された行パーティションをWに格納する手段とを
有する請求項18に記載のコンピュータネットワーク上の装置。
【請求項２０】
当該拡張された行パーティションWを解くためにソルバを適用するステップが：
W内のシングルトンである全ての行レコードの集合、OLP[M]をS(M, Mq)に投影することにより、得られるOLP[M, Mq, B*]を解く手段と；
OLP[M, Mq, B*]の前記戻された解およびB*を使用して、OLP[W]の基底解、B=Basis(W, OLP[M, Mq, B*])を計算する手段とを
さらに有する請求項19に記載のコンピュータネットワーク上の装置。
【請求項２１】
より良い目的関数値が利用可能であるかを決定する手段が：
BestObj<Obj(B)かを決定する手段をさらに有し、Obj(B)が、請求項9の当該基底解Bを使用して計算される前記目的値を格納するためのダブルであり、かつ今までに計算された前記最良の目的値、BestObjがダブルである
請求項19に記載のコンピュータネットワーク上の装置。
【請求項２２】
当該解くための手段が、基底最適な解を戻す場合、オリジナルの線形計画問題の最適な解を戻す
請求項12に記載のコンピュータネットワーク上の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、最適化技法に関する。さらに詳細には、本発明は、大きな消費者意思決定に対する最適な解を提供するための大きな消費者意思決定に関する。
【背景技術】
【０００２】
大きな消費者意思決定は、1つ以上の大域的制約(global constraint)で何百万ものアカウントをおこなう決定により特徴付けられる。この大域的制約を含むということは、全てのアカウントに対する決定が、全て一緒に調べられなければならないことを意味する。学問におけるこのような問題は、その組み合わせがアカウントの数および各アカウントに対する決定選択肢の数に基づいて指数関数的に増加するので、NP困難(NP-hard)問題（それは、0-1線形計画問題(0,1-linear program)として定式化される)として分類されてきた。この問題対する典型的な解を、従来技術による消費者意思決定に対するソルバのコンポーネントを示す線図である図1を参照に、記載することができる。アカウント2データのサンプルまたはセグメントは、ユーザ定義の採点関数(scoring function)およびシステム関数からなる計算器 4への入力として提供される。計算器の出力は、消費者意思決定モデルの0-1線形計画問題の目的、制約を構築するために使用される。線形計画問題の緩和法(relaxation)は、線形計画問題(LP(linear program))ソルバ 8への入力である。LPソルバは、小数部を含むかもしれない解を出力する10。数個のカスタムソルバが、変数の数または許可される制約のタイプに関する制限を強化することが理解されるべきである。
【０００３】
この問題は、この10年の間、すなわち消費マーケティングセクタが消費者に何を提供するべきかという決定を援助する最適化アルゴリズムを使用することに注目し始めてから、存在してきた。例えば、クレジットカード業界は、これらのアルゴリズムの適用において、リーダーであった。
【０００４】
この業界の現在のアプローチは、最適化アルゴリズムを大域的制約を含む大規模な消費者意思決定に適用する時、サンプリングおよびセグメント化法を使用する。サンプリング法において、その解は、サンプルの質に依存する。セグメント化法において、その解は、セグメントの質に依存する。このようなサンプリングおよびセグメント化法は、既存の最適化アルゴリズムおよびコンピュータメモリの制限に基づいて、使用される。ほとんどのアルゴリズムは、全部の問題がメモリにロードされることを要求する。これらの決定問題は、32ビットのアドレス空間に収まらない。時々、1つの大域的制約を要求するのみで、かつ1つの特定タイプの決定のみを解くように解を狭めるような他の方法で、問題を減らすことができるカスタムコードは、書かれた。別のアプローチは、64ビットコンピュータを使用することを含む。しかしながら、このようなコンピュータは、高価であり、かつソルバは、新しいか、または経験が浅い。
【０００５】
全てのこのようなアプローチは、アプローチを利用する人々の経験、およびサンプリング、セグメント化、および／または問題簡約法(reduction technique)の適用性に従い、異なる度合いの成功を達成することが理解されるべきである。いずれも、今日のプロジェクトのために完全には受け入れられない。
【０００６】
特許文献1は、クロス・セリングの多次元最適化の問題に対する反復的アルゴリズムを議論している。ここで議論される技法は、多数のプロモーションMを非常に大きな集合の潜在的顧客Nへ提供する時、非線形の数学的定式化（この非線形性は、ラグランジュ乗数(Lagrange multiplier)を導入することによる）を、解決されることを求められる従来の線形多次元問題に提供することにより、解を記載している。このようなプロセスは、可能性リストの統計的に重要なサンプルをランダムに選択すること、オファーと選択された可能性の各対の効用関数(utility function)の値を計算すること、オリジナルの線形多次元問題を可能な次元数のより小さい問題（なお線形）に縮小すること、所望の許容値で数値的に選択されたサンプルに対してより小さい問題を反復的アルゴリズムを使用して解くこと、および完全な可能性リストに対する1つのパスにおいてオファーの集合を計算するために、その結果を使用することからなる。Galperinら（特許文献1）が、データの1つのサンプルを使用するのみであり、そのデータの全てを使用するわけではなく、かつ最適性、まさに解を保証するわけではないことは理解されるべきである。
【０００７】
非常に大きな最適化問題をアカウントレベルで解くことは、有利であろう。
【０００８】
決定を評価するために使用される、消費者意思決定の構造および基準を利用するアルゴリズムを、全てのデータを考慮しながら、そのアルゴリズムが、ソルバに供給するために、よりはるかに小さい問題を定式化するように、提供することは、有利であろう。
【０００９】
ソルバに供給された問題のサイズを構成することができる方法および装置を提供することは、有利であろう。
【００１０】
ソルバに供給されたより小さい問題を用いるのみで、最初に提起された大域的問題解決法を見つけ出すことができるアルゴリズムを提供することは、さらに有利であろう。
【００１１】
第三者への依存を取り除くソルバを提供することは、有利であろう。
【００１２】
【特許文献１】国際公開第WO0111522号（「クロスセリングマーケッティングキャンペーンの正味の現在価値を最適化する方法(Method for Optimizing Net Present Value of a Cross-Selling Marketing Campaign)）（公開日2001年2月15日）（発明者Y. Galperin、V. Fishman、および L. Gibiansky）
【非特許文献１】「線形計画法(Linear Programming)」、（著者： Vasek Chvata）、（出版社：W.H.フリーマン・アンド・カンパニー(W. H. Freeman and Company)）、1980年
【非特許文献２】「決定最適化用のスケーラブルな正確なアルゴリズム(A Scalable Exact Algorithm For Decision Optimization)」 (2005年6月、改訂)  （フェア・アイザック社内の論文(the internal paper of Fair Isaac Corporation to Maolin Zheng))
【発明の開示】
【課題を解決するための手段】
【００１３】
最適化問題を解くための反復的アプローチが、提供される。各反復は、全部の問題サイズと比較して相対的に小さい副問題を解く。さらに、アルゴリズムは、なお、最初に提起された大域的問題解決法を見つけ出し、このことにより、全体的な大きな消費者意思決定問題へのより良い近似を可能にする。消費者意思決定モデルにおいて、クライアント／顧客は、行レコードにより表される。全部の問題の行レコードを互いに素の部分集合に区分することは、行パーティションと呼ばれる。行パーティション内の要素は、セグメントと呼ばれる。本発明は、以下の4つの基本的動作の反復を提供する；行パーティションを決定する、行パーティションを平衡させる、選択されたセグメントの新しい行パーティションを生成するために拡張する、および新しく生成された行パーティションを解く。方法および装置は、解決動作中に、Dash OptimizationによるDash Optimization Xpressなどの任意の既製の線形計画法ソルバを使用することができる。ソルバに供給された問題のサイズは、制限のあるままでありXpressおよび ILOG社によるILOG CPLEXのような重量級のソルバが、必要とされない、したがって第三者への依存を除去するまで、縮小可能である。このようなソルバは、大きな複雑な問題に対処するために、特殊な発見的方法を、追加することが理解されるべきである。ソルバに供給された問題のサイズは、制限があり、かつ全部の問題のサイズと比較して相対的に小さいままである。したがって、アルゴリズムは、数オーダ−大きな問題を解くことができる。より大きな問題を解くこの能力は、既存のサンプリングおよびセグメント化アプローチがより多くのサンプルおよびセグメントを使用することを可能にし、このことにより、より正確な解を提供する。本発明の1つの実施例において、サンプリングおよびセグメント化法は、問題がアカウントレベルで解かれるまで、取り除かれる。上記の場合、アルゴリズム内で呼び出されるソルバが、最適な解を戻す場合、真の大域的解を達成することに対する疑いが、取り除かれるので、解は、さらに低コストで生成され、かつ最良のリターンは、達成される。
【発明を実施するための最良の形態】
【００１４】
最適化問題を解くための反復的アプローチが、提供される。各反復は、全部の問題サイズと比較して相対的に小さい副問題を解く。さらに、アルゴリズムは、なお、最初に提起された大域的問題解決法を見つけ出し、このことにより、全体的な大きな消費者意思決定問題へのより良い近似を可能にする。消費者意思決定モデルにおいて、クライアント／顧客は、行レコードにより表される。全部の問題の行レコードを互いに素の部分集合に区分することは、行パーティションと呼ばれる。行パーティション内の要素は、セグメントと呼ばれる。本発明は、以下の4つの基本的動作の反復を提供する；行パーティションを決定する、行パーティションを平衡させる、選択されたセグメント新しい行パーティションを生成するために拡張する、および新しく生成された行パーティションを解く。方法および装置は、解決動作中に、Dash OptimizationによるDash Optimization Xpressなどの任意の既製の線形計画法ソルバを使用することができる。ソルバに供給された問題のサイズは、制限のあるままでありXpressおよび ILOG社によるILOG CPLEXのような重量級のソルバが、必要とされない、したがって第三者への依存を除去するまで、縮小可能である。このようなソルバは、大きな複雑な問題に対処するために、特殊な発見的方法を、追加することが理解されるべきである。ソルバに供給された問題のサイズは、制限があり、かつ全部の問題のサイズと比較して相対的に小さいままである。したがって、アルゴリズムは、数オーダ−大きな問題を解くことができる。より大きな問題を解くこの能力は、既存のサンプリングおよびセグメント化アプローチがより多くのサンプルおよびセグメントを使用することを可能にし、このことにより、より正確な解を提供する。本発明の1つの実施例において、サンプリングおよびセグメント化法は、問題がアカウントレベルで解かれるまで、取り除かれる。上記の場合、アルゴリズム内で呼び出されるソルバが、最適な解を戻す場合、真の大域的解を達成することに対する疑いが、取り除かれるので、解は、さらに低コストで生成され、かつ最良のリターンは、達成される。
【００１５】
商業的な利点
企業およびその顧客がより高度な精度で既存の問題を解くこと可能にし、このことにより顧客により大きなリターンを提供する商業的な利点が、提供されることが理解されるべきである。企業が、現在、サンプリングまたはセグメント化法を用いている場合、本発明の1つの実施例は、このようなプロジェクトがより多くのサンプルまたはセグメント、おそらく一桁多いサンプルまたはセグメントを使用することを可能にする。さらに、企業およびその顧客は、クロスセル(cross-sell)のような、大域的制約で、アカウントレベル決定を必要とするプロジェクトに対処することを開始することができる。真のアカウントレベル最適化を強要する現在の技法は、必要とされる局所的制約のタイプに起因してこのようなプロジェクトに十分に対処することができない。現在の技法をクロスセルに適用することは、サンプリング、セグメント化、近似、またはボリュームなどの1つの大域的制約のみを使用する能力の削減を使用する。
【００１６】
概要
本発明の1つの実施例は、本発明による大きな消費者意思決定のためのソルバ12を示す線図、図2を参照して記載可能である。
【００１７】
本発明の1つの実施例は、以下の機能を提供する：
それは、既存のソルバを含む；
それは、全ての処理レベルで使用可能である：
アカウント；
サンプル；および
セグメント。
【００１８】
それは、反復的方法で4つの主動作を使用する：
行パーティションを見つけ出す；
行パーティションを平衡させる；
新しい行パーティションを生成するために、行パーティションを拡張する；および
新しく生成された行パーティションを解く。
【００１９】
本発明の1つの実施例の高レベルの流れは、図3、スケーラブルな正確なアルゴリズムの流れ図100を参照して、記載可能である。アルゴリズムは、入力問題の最初の解を計算すること(102)から始まる。最初の解を現在の解として設定する。次に、アルゴリズムは、以下に従って進む：(1) 現在の解に基づく行パーティションを決定する、または見つけ出す(104)。(2) 行パーティションを見つけ出した後、行パーティションを平衡させる(106)。平衡させられた行パーティションにおいて、全ての非シングルトンのセグメントを拡張されないまたは「使用可能」としてマークする。(3) セグメントの間で、任意の使用可能なセグメントが存在するかを決定する(108)。もしそうでない場合、アルゴリズムは、終了する (110)。(4) 使用可能なセグメントが存在する場合、限られた数の（予め設定された）このようなセグメントを選択し、かつそれらをシングルトンに拡張する(112)。新しい行パーティションを、生成する。(5) 新しく生成された行パーティションを解くために、ソルバを適用する(114)。次に、解かれた行パーティションが与えられた場合、アルゴリズムは、より良い目的関数値、またはより良い解が、得られるかを決定する (116)。もしそうである場合、アルゴリズムは、現在の解をアップデートするために、ソルバから戻された解を使用し、かつ(1)へ行く。もしそうでない場合、制御は、(3)へ行く。
【００２０】
典型的なスケーラブルなアルゴリズム
本明細書で提案されるアルゴリズムは、アカウントレベル定式化用であり、かつサンプルで重みを付けられた、セグメント定式化に適用可能である。簡略化のために、任意のアカウントからの処理の除外(exclusion)は存在しないと仮定する。もしそうでない場合、それは、アルゴリズムの実施において、処理可能である。
【００２１】
新しいアルゴリズムは、反復的アプローチをとる。各反復において、それは、以下に定義される、Bに関するMの「部分(fractional)」セグメントがシングルトンであるように、OLP[M]の行パーティションMおよび基底解Bを、維持する。次に、アルゴリズムは、行パーティションに基づいて構築されたより小さい線形計画問題を解くことにより、Mをさらに正確にすることを試みる。新しいアルゴリズムは、第三者線形計画問題ソルバによるメモリ使用を、劇的に縮小する。一般に、第三者ソルバのメモリ使用は、新しいアルゴリズムにとってボトルネックとならないであろう。それは、パワフルでないが頑強な他の第三者線形ソルバを使用することへの扉を開く。
【００２２】
次の数個のサブセクションにおいて、主アルゴリズムのビルディング・ブロックとして働く、いくつかの必要な概念および少数の原子動作(atom operation)またはサブルーチンが、導入される。
【００２３】
（アカウントレベル線形計画問題定式化）
アカウントレベル定式化の線形緩和法を、ここで述べられるOLP（オリジナルの線形計画問題(original linear program)）として表す：
2008506197.tif 000002
ここで、 I は、アカウントのインデックス集合、Tは、処理のインデックス集合、およびGは、大域的制約のインデックス集合である。
【００２４】
このOLPを、ペナルティ変数を各大域的制約に加えることにより、以下のように再び定式化する：
2008506197.tif 000003
ここで、各 ps は、満足しない大域的制約に対してペナルティ重みとして働く極端に大きな正の数である。OLPは、この定式化を表すために、なお、使用可能である。両方の定式化は、第1の定式化が解を有する場合、等価である。しかし、第2の定式化は、それが、常に解を有するという利点を有する。本明細書において述べられるアルゴリズムは、第2の定式化をその入力フォーマットとして使用する。
【００２５】
（行パーティションからの線形計画問題）
MAXSIZEを行パーティション内のセグメントの最大のサイズを表す正の一定の整数とする。それを、今から、1000として設定する。
【００２６】
M= {M1,M2,…Mk}を、全部の入力行レコードの行パーティション（または入力アカウント）とする。| Mq |をMqの基数、またはMqの度数を表すとする。セグメントが、唯1つの要素を含む場合、それは、シングルトンと呼ばれる。さらにまた、Tを可能な処理のインデックス集合とする。
2008506197.tif 000004
および
2008506197.tif 000005
とする。ここで、
2008506197.tif 000006
および
2008506197.tif 000007
は、OLP内と同じである。
【００２７】
OLP[M]は、以下の線形計画問題、Mに基づいたセグメント定式化を表すとする：
2008506197.tif 000008
【００２８】
Bは、OLP[M]の解とする。それは、Bのコンポーネントが、2つの部分：基底および非基底に区分可能である場合、基底解と呼ばれる。非基底コンポーネントは、本明細書における問題に対して、ゼロであり、かつ、基底コンポーネント、または基底変数に対応する、OLP[M]の係数マトリクスの列は、（独立ベクトルとして）最大の独立集合を形成する。基底解は、存在する（非特許文献1を参照）。このような概念は、最適な解を得るためのアルゴリズムに極めて重要である。Bを  OLP[M]の基底解とする。M内のセグメントMqに対して、bvidex(Mq )={j| if yqj is a basic variable in B}とする。それは、Mqの基底処理インデックス集合と呼ばれる。bvidex(Mq )が1つの、より多い要素を有する場合、Mq は、Bに関する「基底部分(basic fractional)」(要約すれば、「部分(fractional)」)セグメントと呼ばれる。以下に定義されるMに関する、「再平衡(re-balancing)」動作は、これらの非部分(non- fractional)セグメント、すなわち、1つの要素のみを含む、それらの基底処理インデックス集合のためである。この動作は、非部分セグメントのサイズをチェックする。d が 実数である場合、
2008506197.tif 000009
は、d以上である最も小さい整数を表す。
【００２９】
2008506197.tif 000010
2008506197.tif 000011
【００３０】
全ての平衡動作が、これらの非部分セグメントに関して実行されることに留意されたい。再平衡後、新しい行パーティションが、生成される。この新しく生成された行パーティションに対して、以下のルーチンは、BからOLP[Re-balancing(M,B)]の基底解を計算する。
2008506197.tif 000012
【００３１】
以下の動作／サブルーチンは、MのセグメントMqを、それが含む個別のレコードと取り替ええることにより、行パーティションMを新しいものに拡張する。
2008506197.tif 000013
【００３２】
B = {vqj、ys } は、OLP[M]の基底実行可能解とし、およびMqは、Bに関する非部分セグメントとする。S(M、Mq)は、Expanding(M、Mq)におけるシングルトンの集合とする。M*は、Expanding(M、Mq)のこれらの非シングルトンセグメントの集合を表す。OLP[M、Mq,B]を、以下のように、OLP[M]およびOLPから演繹される線形計画問題であると定義する：
2008506197.tif 000014
【００３３】
OLP[M,Mq,B]が、S(M,Mq)に関して定義されることが理解されるべきである。OLP[M,Mq,B]が、OLP[M]をS(M,Mq)上に投影することにより得られることは、直感的に理解される。それは、実行可能解を有する（h∈S(M,Mq)および h □（元として含まれない）Mq ならば、h ∈Mq および zhj =vhj に対して、zhj= (1/|Mq|)vqj とする場合、実行可能解が得られ、かつそれは、Bと同じ目的値を有する)。
【００３４】
W=expanding(M、Mq)およびB’を、OLP[M,Mq,B]の基底解とする。Basis(W、OLP[M、Mq ,B]) は、{vhj|h in M*}∪B’を表すとする。Basis(W, OLP[M, Mq ,B]) は、OLP[W]の基底解であることを、示すことができる。この表記法は、以下に記載される主アルゴリズムにおいて、使用される。
【００３５】
（基底解に基づく行パーティション）
Mがトリビアルな行パーティションである、すなわち各セグメントが1つのアカウントを含む場合、前のサブセクションで使用された同じ表記法により、OLP=OLP[M]である。今後、アカウントレベル定式化は、行パーティションまたはセグメント定式化の特殊なケースに他ならないものとして理解可能である。
【００３６】
Mは、行パーティションであるとする。B={xij,ys}は、OLP[M]の基底解であるとする。各セグメントに対して、それは、Bに基づいて前のサブセクションにおいて定義された基底処理インデックス集合を有する。Bの全ての非基底コンポーネントは、ゼロである。ここで、Bに基づいて行パーティションを生成する次の動作またはサブルーチンは、以下のように表わされる：
2008506197.tif 000015
2008506197.tif 000016
【００３７】
マージ動作が、Bに関する非部分セグメントに関して実行されるのみであることが理解されるべきである。この事実に基づいて、以下のサブルーチンは、OLP[Segments(M,B)]の基底解を計算する：
2008506197.tif 000017
【００３８】
（セグメントレベル解を構成要素に分解する）
Mは、行パーティションであり、かつB={vij,ys } は、OLP[M]の最適な解である。さらにまた、I は、アカウントのインデックス集合とし、かつT は、処理のインデックス集合とする。P は、Mのセグメントのインデックス集合とする。BをOLPの解を構成要素に分解する具体例サブルーチンを、以下に示す：
2008506197.tif 000018
【００３９】
（OLPの最初の基底解を計算する）
このサブセクションにおいて、OLPの基底解を計算する方法が、提案される。
2008506197.tif 000019
2008506197.tif 000020
【００４０】
アルゴリズムの具体例のプロトタイプにおいて、極めて最初の行パーティションは、以下のように、生成される：
大域的制約を考慮することなく、各行レコードまたはアカウントに対して最良の処理を割り当てる。次に、行レコードまたはアカウントを、2つの行レコードが、それらが同じ処理を割り当てられた場合、同じ部分集合にあるように、割り当てられたそれらの処理に従って区分する。次に、望ましい行パーティションを生成するように、行パーティションを平衡させる。
【００４１】
サブルーチンにおける線形計画問題のサイズは、基底解に関する少数の部分セグメントが存在するのみであるという事実と共に、セグメントの最大のサイズによりコントロール可能である。このことは、線形計画問題OLP[W]が、大きくなく、かつ第三者線形計画問題ソルバにより、効率的に解くことが可能であることを意味する。
【００４２】
（アルゴリズム）
アルゴリズムは、OLPの基底解を用いて始まり、第三者線形計画問題ソルバを呼び出すことにより、一連の線形計画問題解き、およびOLPの解に到達する。第三者ソルバが、各呼び出しにおいて、最適な、基底解を戻す場合、アルゴリズムは、最適な解をOLPに戻すであろう。副産物として、それは、また、最適な行パーティションも見つけ出す、すなわち、この行パーティションに基づく線形計画問題の最適な解は、OLPの最適な解に、変換可能である、または構成要素に分解可能である。
【００４３】
アルゴリズムは、図4、アルゴリズムのワークフロー図を参照して、以下に示される対応する擬似-コードと共に、記載可能である。アルゴリズムは、本明細書では、ZASGA (Zheng Account-Segment-Generation Algorithm)と呼ばれる。ZASGAは、ソフトな制約設定のために働く、すなわちペナルティ重みは、大域的制約とビジネス目的間のトレードオフを同程度に考慮して、相対的により小さくなるように設定可能である。最初の入力に対して、OLPは、アカウントレベル情報を使用して、例えば、Ｆａｉｒ  Ｉｓａａｃ  Ｃｏｒｐ．’ｓ  Ｄｅｃｉｓｉｏｎ  Ｏｐｔｉｍｉｚｅｒにより、計算される402。アルゴリズムの出力は、行パーティションおよびOLPの解である 412。戻された解は、最適である、または上記のソルバZASGA呼び出しに全てを依存しない。
【００４４】
（ZASGA 擬似-コード）：
入力：アカウントレベル情報を使用することにより計算されたOLP 402。
出力：行区分およびOLPの解 412。
データ対象定義：
B：基底解を格納するためのダブル配列。
B*：基底解を格納するためのダブル配列。
M,W：セグメント化を格納するためのベクトルの集合。
Obj(B)：基底解Bを使用して計算された目的値を格納するためのダブル。
BestObj：今までに計算された、ダブルの、最良の目的値、負の無限大に初期化される。
Mark：「使用可能な」および「使用不能な」セグメント情報を表すMと同じ長さを有するブール配列。
MAXSIZE：セグメントの最大のサイズを表す一定の整数。
NUMITERATIONS：大きな整数となるように設定する、それは、主ループの可能な反復の
制限である。
【００４５】
アルゴリズム本体：
2008506197.tif 000021
【００４６】
この方法が、線形計画問題の入力は劣化されないと仮定していることが理解されるべきである。この場合、線形計画問題の入力が、劣化され、かつ方法内で呼び出されたソルバが、基底最適な解を戻す場合、オリジナルの線形計画問題の最適な解を保証するために、もう1つの簿記ステップ(book-keeping step)が、加えられる必要がある：すなわち最後の416の後に、基底解B=Basis(W, OLP[M, Mq, B*]を構成要素に分解し、オリジナルの線形計画問題の基底解、すなわちB^を得る。もしB^が、現在の最良の解と異るが、しかしその目的値が、現在の最良の解のそれと同じ可能性がある場合、WおよびBを格納する、すなわち保持する。次に、方法を終了する前に、格納されたWおよびBが存在するかチェックする。もしそうである場合、現在の解および行パーティションを、格納されたBおよびWと取り替え、かつ406に進む。そうでなければ方法を終了する。
【００４７】
上記アルゴリズムのステップの詳細な証明を参照するために、その論文が本明細書に参照として組み込まれている非特許文献2を参照されたい。
【００４８】
動作／サブルーチンRe-balancing(M)が、アルゴリズム内の全ての中間の線形計画問題を、予測がつくサイズに保持することが理解されるべきである。このようなことは、アルゴリズムのスケーラビリティに非常に重要である。さらに、アルゴリズムにおいて、唯1つの非シングルトンは、選択され、各反復において拡張する。実際に、数個のこのようなセグメントは、そうすることが可能な十分なコンピュータメモリが存在する場合、合計の反復の数を縮小するために、同時に、選択され、拡張することが可能である。
【００４９】
「Solve OLP[M, Mq ,B*]」においてソルバ呼び出された動作416が、副線形計画問題OLP[M, Mq, B*]の基底最適な解を戻す場合、アルゴリズムは、オリジナルの線形計画問題OLPの最適な解を戻すことが理解されるべきである。
【００５０】
（混合整数計画問題を解く）
本発明の1つの実施例において、大きな消費者意思決定問題は、0-1線形計画問題（OLP内の全ての決定変数を、0,1として制限する場合）として定式化され、かつその線形緩和法を解くアルゴリズムを提案する。
【００５１】
ZASGAのリターンからMおよびB=disAggregating(M,B*)を取り出すと、Bが少数部を含まない場合、Bは、大きな消費者決定問題に対する整数解である。そうでなければ、全ての部分セグメントは、シングルトンである。多くて|G|のこのような部分の数がBに存在する（ここで、|G|は、大域的制約の数である）ことが、証明可能である。詳細な証明を参照するために、その論文が本明細書に参照として組み込まれている非特許文献2を参照されたい。例えば、2百万のアカウントおよび4つの大域的制約が存在する場合、結果は、多くて、部分割り当てを有する4アカウントである。これらの小数部をこれらの最も近い整数に丸めることにより、整数解が、得られる。それは、最適なまたは実行可能でないかもしれない。しかし、誤差は、問題のスケールと比較して、相対的により小さい。整数解を得る別の方法は、第三者のMIPソルバを呼び出すことによりOLP[M]を解き、かつ解をアカウントレベル解に構成要素に分解することである。OLP[M]が、相対的に小さいので、MIPソルバは、それを解くであろう。構成要素に分解された解は、最適でないかもしれないが、極めて優れたものであろう。最適な、またはそうでない、解の質は、アルゴリズム内で呼び出されたソルバに依存する。
【００５２】
具体例の結果
表Aは、コンピュータ環境：1.2 GHz CPU、1.2 GB RAM、Windows 2000（登録商標）を使用し、かつ全ての実行に対して12個の処理および4個の大域的制約を適用した結果を示す。
表 A
2008506197.tif 000022
【００５３】
表 B は、コンピュータ環境：1.2 GHz CPU、1.2 GB RAM、Windows 2000（登録商標）を使用し、かつ全ての実行に対して12個の処理および4個の大域的制約を適用した結果を示す。
表 B
2008506197.tif 000023
【００５４】
本明細書において提供された方法およびプロセス使用する企業への利益が、プロジェクトに対するより良い精度につながる、より多くのサンプル、例えば、より良い予測、増加した制約満足度、および増加したクライアント満足度および変換割合を含むことは、上述の議論および結果から明らかである。より多くのセグメントは、処理のより良い細分化、例えば、より良い予測、縮小されたモデルおよび予測誤差、および増加したクライアント満足度および戦略コントロールにつながる。
【００５５】
本発明の1つの実施例が、動作を並列に実行することが理解されるべきである。内部ループの処理を拡張および解決動作を独立して動作するスレッドに分割することは、可能である。
【００５６】
本発明の別の実施例は、拡張するために使用可能なセグメントを見つけ出すための代替選択アルゴリズムを使用する。
【００５７】
本発明の別の実施例は、基底実行可能解を導入するための代替アルゴリズムを使用する。
【００５８】
本発明の別の実施例は、LPソルバに供給するために使用されるキャッシュサイズを調整する。
【００５９】
従って、本発明が、特定の好適実施例に関して詳細に記載されたが、本発明が関連している技術分野の通常の当業者は、特許請求の範囲の精神および範囲から逸脱することなく、様々な修正および強化を実施できること、を理解するであろう。
【図面の簡単な説明】
【００６０】
【図１】従来技術による消費者意思決定のためのソルバのコンポーネントを示す線図である。
【図２】本発明による大きな消費者意思決定のためのソルバを示す線図である。
【図３】本発明によるスケーラブルな正確なアルゴリズムの流れ図である。
【図４】本発明によるスケーラブルな正確なアルゴリズムの詳細な流れ図である。
【符号の説明】
【００６１】
102  最初の解を計算する
104  行パーティションを見つけ出す
106  行パーティションを平衡させる
116  より良い目的関数値が、得られるか？
108  拡張されない非シングルトン？
114  行パーティションを解く
112  行パーティションを拡張する
110  終了
【図１】
2008506197.tif 000024
【図２】
2008506197.tif 000025
【図３】
2008506197.tif 000026
【図４】
2008506197.tif 000027
【国際調査報告】
2008506197.tif 000028