(57)【要約】ジェネレータ構成要素、ソルバー構成要素、シミュレーション構成要素及び可視化構成要素である少なくとも4つの構成要素を提供するように構成されたデータ管理のためのコンピュータシステムであって、シミュレーション構成要素は確率的プロセスをシミュレートし、シミュレートされたプロセスのシミュレーションデータをジェネレータ構成要素に出力するように構成され、ジェネレータ構成要素はモデル入力を処理してこれから動的確率計画(DSP)を生成し、更にシミュレータ構成要素から受け取られたシミュレーションデータを処理し、処理されたシミュレーションデータと共にソルバー構成要素にDSPを出力するように構成され、ソルバー構成要素はDSPと処理されたシミュレーションデータを受け取り、シミュレーションデータと共にDSPを処理するように構成され、可視化構成要素はソルバーによって処理されたデータを可視化することができるように構成される。【選択図】図２
2008501171.tif 000002
【特許請求の範囲】
【請求項１】
動的確率計画法問題を解くためのデータ管理方法であって、
前記方法が、
問題を反復的に解くことを可能にする構成要素のスイートを提供する段階を含み、
前記構成要素は、ジェネレータ構成要素、ソルバー構成要素、シミュレーション構成要素、及び可視化構成要素を含み、
ｉ．前記ジェネレータ構成要素は、モデル入力から動的確率計画（ＤＳＰ）を生成し、前記シミュレーション構成要素の出力を変換して前記ソルバー構成要素によって処理するように構成され、
ｉｉ．前記ソルバー構成要素は、前記ＤＳＰを処理するように構成され、
ｉｉｉ．前記シミュレーション構成要素は、前記ジェネレータ構成要素によって処理するための確率的プロセスをシミュレートするように構成され、
ｉｖ．前記可視化構成要素は、前記入力モデルの出力と前記ソルバーによって生成された結果とを提供する、
ことを特徴とする方法。
【請求項２】
前記シミュレーション構成要素は、各々が予め定められた特性をシミュレートするように構成された複数のシミュレータを提供することを特徴とする請求項１に記載の方法。
【請求項３】
前記可視化構成要素は、複数のビューワを含むことを特徴とする請求項１又は請求項２に記載の方法。
【請求項４】
前記可視化構成要素内のビューワを前記シミュレーション構成要素内のシミュレータと結合することを特徴とする請求項２に従属する請求項３に記載の方法。
【請求項５】
前記可視化構成要素を使用して解の不足を識別し、適切な改良を用いてプログラムを再実行する段階を含む前記請求項のいずれかに記載の方法。
【請求項６】
前記ＤＳＰに対するモデル入力を反復的に修正する段階を含む請求項５に記載の方法。
【請求項７】
前記ＤＳＰを解きながら、前記ジェネレータ構成要素にモデルを区分的に読み込ませる段階を含む前記請求項のいずれかに記載の方法。
【請求項８】
前記ＤＳＰをサブタスクに分割する段階を含む前記請求項のいずれかに記載の方法。
【請求項９】
前記ＤＳＰのソルバーサブタスクに読み込むように前記ジェネレータ構成要素に行わせることを特徴とする前記請求項のいずれかに記載の方法。
【請求項１０】
前記ソルバー構成要素内の前記ソルバーは、複数のプロセッサにわたって並列化をサポートすることを特徴とする前記請求項のいずれかに記載の方法。
【請求項１１】
前記可視化構成要素は、前記ジェネレータ構成要素内のデータ構造体にアクセスすることを特徴とする前記請求項のいずれかに記載の方法。
【請求項１２】
特定のアプリケーション用の専用に生成されたサブ構成要素、前記シミュレータ構成要素、及び／又は前記可視化構成要素でカスタマイズ及び／又は部分的置き換えを行う段階を含む前記請求項のいずれかに記載の方法。
【請求項１３】
他の構成要素によって呼び出すことができるプログラムのライブラリを提供するライブラリ構成要素を提供する段階を含む前記請求項のいずれかに記載の方法。
【請求項１４】
ＤＳＰからモデルを分離する段階を含む前記請求項のいずれかに記載の方法。
【請求項１５】
ジェネレータ構成要素、ソルバー構成要素、シミュレーション構成要素、及び可視化構成要素である少なくとも４つの構成要素を提供するように構成されたデータ管理のためのコンピュータシステムであって、
前記シミュレーション構成要素は、確率的プロセスをシミュレートし、シミュレートされたプロセスのシミュレーションデータを前記ジェネレータ構成要素に出力するように構成され、
前記ジェネレータ構成要素は、モデル入力を処理してこれから動的確率計画（ＤＳＰ）を生成し、更に前記シミュレータ構成要素から受け取られたシミュレーションデータを処理し、前記ソルバー構成要素に対して前記処理されたシミュレーションデータと共に前記ＤＳＰを出力するように構成され、
前記ソルバー構成要素が、前記ＤＳＰと前記処理されたシミュレーションデータとを受け取り、前記シミュレーションデータと共に前記ＤＳＰを処理するように構成され、
前記可視化構成要素が、前記ソルバー構成要素によって処理された前記データを前記ソルバー構成要素の出力と共に可視化することができるように構成される、
ことを特徴とするコンピュータシステム。
【請求項１６】
コンピュータ上で読み込まれたときに、当該コンピュータに請求項１から１４のいずれかの方法を提供させる命令を含む機械読み取り可能媒体。
【請求項１７】
コンピュータ上に読み込まれたときに、コンピュータに請求項１５のコンピュータシステムを提供させる命令を含む機械読み取り可能媒体。
【請求項１８】
実質的に本明細書で説明され添付図面に示された動的確率計画法問題を解くためのデータ管理方法。
【請求項１９】
実質的に本明細書で説明され添付図面に示されたデータを管理するためのコンピュータシステム。
【請求項２０】
動的確率計画法問題を解くように構成されたプログラムであって、前記プログラムが、前記問題を反復的に解くことができる構成要素のスイートを提供し、前記構成要素は、ジェネレータモジュール、ソルバーモジュール、シミュレーションモジュール、及び可視化モジュールを備え、
ｉ．前記ジェネレータモジュールは、モデル入力から動的確率計画（ＤＳＰ）を生成し、前記シミュレーションモジュールの出力を変換して前記ソルバーモジュールによって処理するように構成され、
ｉｉ．前記ソルバーモジュールは、前記ＤＳＰを処理するように構成され、
ｉｉｉ．前記シミュレーションモジュールは、前記ジェネレータモジュールによって処理するための確率的プロセスをシミュレートするように構成され、
ｉｖ．前記可視化モジュールは、入力モデルの出力と前記ソルバーモジュールによって生成された結果とを提供する、
ことを特徴とするプログラム。
【請求項２１】
請求項２０に記載のプログラムを提供する命令を含む機械読み取り可能媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ操作のためのコンピュータシステムに関し、詳細には、限定ではないが、データを操作して将来動向を解明するよう構成されたコンピュータシステムに関する。これに関連する方法も提供される。
【背景技術】
【０００２】
１９５０年代半ば以降、線形計画最適化、より一般的には数理計画最適化技術が、現在のコンピューティングシステムで安定的に商業利用されている。１９７０年代の半ば頃、数理計画法におけるモデリング言語の概念が米国エネルギー省と世界銀行で別々に生まれた。
【０００３】
このような言語におけるモデル表現は数理プログラムの数値最適化に対するものであり、その相似形は、データベース管理システムスキーマが単層ファイルに対するものである。モデルの数理記述をソルバーすなわち最適化ルーチンと直接伝達するモデル化言語でのステートメントに変えることは、アナリストにとって直截的なものである。
【０００４】
この間の数年で、様々な高度なモデル化言語が、実際上の計画問題に関する大規模な決定論的な線形、非線形、及び不連続性の最適化モデルの作成、解法、及び修正のために日常的に使用されるようになった。
【０００５】
動的確率計画法
動的確率計画法（ＤＳＰ）は、現在及び将来の不確実性を伴う計画問題を解く数値的方法である。一般的に、この方法は、数理プログラミング言語で問題を記述する段階と、当該計画を適切なソルバーに渡す段階とを含む。しかしながら、このような問題を解くことは、計算集約的であり、許容可能な時間で現実性のある問題を解くことは殆ど不可能になる。この方法の現在の困難性は、本発明のＤＳＰツールに関する幾つかの課題に由来している。従って、これまでは現在及び将来において不確実性を伴うこのような問題を許容可能な時間で解くことには問題があり、或は全くできなかった。将来に関しての予想を行う目的でこのような問題を解くことについての要望がある。このような予想は、エネルギー、石油、又は通信帯域幅、或いは金融市場での供給と需要を含む広範な分野で有用である。帯域幅、エネルギー、石油及び同様のものに対する要求についての将来予想は、建設するプラントの規模などを判断する上で有用とすることができる。
【０００６】
世界の不確実な将来の状態を表現する方法に関する課題がある。一般に、これは、将来の代替シナリオを予測するシミュレーションによって行われる。確率計画法は、これらの代替シナリオの全てを決定論的等価問題（ＤＥＰ）に組み合わせることを含む。シナリオが少なすぎる場合には解がロバストではなく、シナリオが多すぎる場合には、適正な時間内に解くことができないといった問題がある。これは、複数の時間ステップがあり、多くのシナリオが幾何級数的に成長するＤＳＰで特に問題となる。
【０００７】
第２の課題は、適切なソルバー、すなわち問題の特性に適合するものを選択することである。汎用のソルバーは、メモリにＤＥＰ全体をマッピングしようとし、実行者は非現実的なほど単純なＤＥＰ又は大容量のメモリに制約され、より複雑なＤＥＰを解くために計算能力が要求されることになる。従って、現在容易に利用可能な演算能力を用いて現実的な問題を適正な時間内にどのように解くことができるかに関して問題が生じる。
【発明の開示】
【０００８】
本発明の第１の態様によれば、動的確率計画法問題を解くためのデータ管理方法が提供され、該方法は、ＤＳＰを反復的に解くことを可能にする構成要素のスイートを提供する段階を含み、該構成要素は、ジェネレータ構成要素、ソルバー構成要素、シミュレーション構成要素、及び可視化構成要素を含み、
ｉ．ジェネレータ構成要素は、モデル入力から動的確率計画（ＤＳＰ）を生成し、シミュレーション構成要素の出力を変換してソルバー構成要素によって処理するように構成され、
ｉｉ．ソルバー構成要素は、ＤＳＰを処理するように構成され、
ｉｉｉ．シミュレータ構成要素は、ジェネレータ構成要素によって処理するための確率的プロセスをシミュレートするように構成され、
ｉｖ．可視化構成要素は、入力モデルの出力とソルバーによって生成された結果を提供することを特徴とする。
【０００９】
このような本方法の利点は、従来の解に対し等価なハードウエア上で動作する現実世界の計画問題に対する動的確率計画法（ＤＳＰ）の効率及び有効性を改善することができることである。構成要素は、統合ツールセットを用いてロバストな解を求める反復的なプロセスの段階をサポートすることによって、問題のサイズ及び複雑さに関し従来の至難な課題を解決することができ、該統合ツールセットは、各モデル化タスク、すなわちシミュレーション、生成、最適化、及び可視化について特別に設計される。
【００１０】
可視化構成要素が入力モデルとソルバーによって生成された結果の両方を見ることができ、これによりＤＥＰに対する解が許容可能であることをユーザが確認することが可能となるので有利である。入力モデルとソルバーによって生成された結果を比較することによって、ＤＥＰに対する満足な解が得られるまで反復プロセスを行うことが可能となる。
【００１１】
構成要素は、反復プロセスのＤＳＰを使用して現実世界の計画問題を解くための統合ツールセットを提供するものと考えることができる。ＤＳＰを解くのに使用される他の数理プログラミング言語は、プログラムが構文的に正しい場合には該プログラムは正確に作成されており、更に解が全て計算することができる場合には解は正しいと仮定する点で、該言語はシングルショットのものである。これまで、解を改良するあらゆる試みは、プログラムを編集し再実行する実行者に委ねられていた。
【００１２】
本方法は、様々なモデル、シナリオ構造体、及びシミュレータデータを用いた反復改良プロセスで得た解を提供することができる。
【００１３】
シミュレーション構成要素は、各々が予め定められた特性をシミュレートするように構成された複数のシミュレータを提供することができる。可視化構成要素は、複数のビューワを含むことができる。本方法は、可視化構成要素内のビューワをシミュレータ構成要素の１つ又はそれ以上のシミュレータと結合することができる。可視化構成要素を使用して、解の不足を識別し、適切な改良を用いてプログラムを再実行することが可能である。
【００１４】
幾つかの、場合によっては最も簡単な実施形態において、可視化構成要素は、テキストファイル又は同様のものとすることができるファイルを見ることが可能なビューワとすることができる。他の実施形態では、ビューワは、より複雑とすることができ、グラフィカルインターフェースを提供することができる。
【００１５】
ジェネレータ構成要素は幾つかの利点を有し、その少なくとも一部は、第１に計画問題の作成を将来のシナリオ構造体から分離させることができることである。これは、確率計画法の分野では革新的なことであり、他の手法では、シナリオ自体がＤＳＰにない場合には全ての構造を埋め込んでいた。このような埋め込みは、ＤＳＰが解くことができるようにＤＥＰにコンパイルされる必要があるので、他の場合には不可避のようである。
【００１６】
本方法は、シナリオ構造体を反復的に修正することが可能であり、解のロバスト性とソルバーの計算効率を改善するのに役に立つ点で有利である。構造をプログラムに埋め込むことを伴う他の全ての手法では、この構造を変更することは、反復することは勿論一度だけでも困難で冗長なものである。これまでハードコードされたものは、本方法のジェネレータ構成要素内で独立し且つ柔軟性がある。従って、確率計画問題は、あたかも決定論的に動的なものであるように確率的プログラミング言語で作成することができ、シナリオ構造体に不確実性が表される方法とは殆ど又は全く関連性がない。
【００１７】
第２に、本方法は、ＤＳＰを解きながら、ジェネレータ構成要素にシナリオを区分的に読み込ませることができる。全ての他の確率計画法ツールは、後で分解ソルバーに渡されても全てのＤＥＰを生成する。これは、解くことができる計画問題のサイズを厳密に制約する。従って、ＤＳＰを解くために必要とされるメモリ及び処理能力がより少ないことは、本方法の利点である。この制約は、世界の将来の状態に適切な範囲に及ぶのに必要とされるシナリオの数が実際に極めて多い可能性があるＤＳＰにとって特に厳しいことである。結果として、他の手法では、仮にあったとしても現実的なＤＳＰを許容可能な時間内に解くことはできない。
【００１８】
本方法は、ＤＳＰをサブタスクに分割することができる。更に、ジェネレータ構成要素は、本方法により、ＤＳＰのサブタスクをソルバー構成要素中に読み込むようにさせることができる。これは、コンピューティングリソースのより効率的な利用を提供することができ、ソリューションプロセスを並列化するよう実行可能にする。この手法は、ジェネレータ及びソルバー構成要素によるサブタスクソリューションの緊密な結合によって促進される。結合されない（サードパーティの）ソルバーを含む他の全ての手法は、全部のＤＥＰを強制的にインスタンス化させる。
【００１９】
ソルバー構成要素は、以下のもの：すなわち、厳密な線形制約を有するＤＥＰ構造に適切なネストされたベンダーアルゴリズム、凸型非線形目的、発見的集合技法、完全な情報の期待値に基づく連続重要性サンプリング、及びジェネレータ構成要素との緊密な結合（上述のような）の様々な適合のいずれかを利用することができる。これらの適合の利点は、ＤＳＰを解く速度と解くことができる計画問題の規模の両方が増大することである。
【００２０】
更に、ソルバー構成要素内のソルバーは、複数のプロセッサにわたって並列化をサポートし、解くことができる問題の規模と解法の速度とを更に増大させることができる。構成要素が設計された現実世界のＤＳＰのタイプにおいて、ソルバー構成要素は他のソルバーよりも１０〜１００倍高速とすることができるベンチマークテストが示された。
【００２１】
本方法は、可視化構成要素がジェネレータ構成要素内のデータ構造にアクセスするのを可能にすることができる。このような方法の利点は、外部ビューワ、すなわちジェネレータ構成要素内のデータ構造にアクセスしないビューワを提供するのに比べて、より迅速でインタラクティブなインターフェースを実現可能なことである。
【００２２】
予測期間に向けて経時的に変化するときに期待される金融ポートフォリオ構成を表示するために、特定のアプリケーションに対する可視化構成要素内のビューワの１つ又はそれ以上をカスタマイズするのが一般的である。本方法により、構成要素に対する直接的結合のより少ない外部ビューワを使用することができ、有利には、モデルが安定化したときに使用される。
【００２３】
本方法により、シミュレーション構成要素及び／又は可視化構成要素が特定のアプリケーション用にカスタマイズされ、又は予め定められたタスクのために特別に生成されたサブ構成要素と部分的に置き換えることができる。
【００２４】
本方法はまた、他の構成要素によって呼び出すことができるルーチンのライブラリを提供するライブラリ構成要素を提供することができる。このようなライブラリ構成要素は、機能性と他の構成要素のデータに対して効率的なインターフェースを可能にするので、このようなカスタマイズを容易にする。ライブラリ構成要素は、本方法によって使用される構成要素を結合するのに役立ち、現実世界の計画問題で使用するために本方法をより効率的にする。本方法は、ＤＳＰからシナリオ構造体を分離することができ、問題の作成及び解に容易且つ迅速な手法を提供する。
【００２５】
ツリーの各ノードが代替シミュレートされたシナリオの観点から将来を評価する必要のある決定ポイントを表すツリーとしてＤＳＰを表現するのが一般的である。このツリーは、シナリオツリーと呼ぶことができ、シミュレートされたシナリオは、ツリーを通る１つの特定の経路を表す。
【００２６】
確率的スイートは、プログラム言語及び個別のシナリオツリー構造で表現された、ＤＳＰのノード構造を利用する幾つかのソルバーを含む。これらのソルバーは、他の汎用ソルバーよりも１０〜１００倍速い、大きな問題を解く速度の大幅な増大を実現する。これは、現実世界の問題を許容可能な時間内に解くことを可能にするばかりでなく、他のソルバーを使用しては解くことができない複雑な問題を容易に解くことも可能にする。
【００２７】
本発明の第２の態様によれば、ジェネレータ構成要素、ソルバー構成要素、シミュレーション構成要素、及び可視化構成要素である少なくとも４つの構成要素を提供するように構成されたデータ管理のためのコンピュータシステムであって、
シミュレータ構成要素は、確率的プロセスをシミュレートし、シミュレートされたプロセスのシミュレーションデータをジェネレータ構成要素に出力するように構成され、
ジェネレータ構成要素は、モデル入力を処理してこれから動的確率計画（ＤＳＰ）を生成し、更にシミュレータ構成要素から受け取られたシミュレーションデータを処理し、プロセスシミュレーションデータと共にソルバー構成要素にＤＳＰを出力するように構成され、
ソルバー構成要素が、ＤＳＰと処理されたシミュレーションデータを受け取り、シミュレーションデータと共にＤＳＰを処理するように構成され、
可視化構成要素は、ソルバーによって処理されたデータを可視化することができるように構成されることを特徴とするコンピュータシステムが提供される。
【００２８】
本発明の第３の態様によれば、コンピュータ上に読み込まれたときに、コンピュータに本発明の第１の態様の方法を提供させる命令を含む機械読み取り可能媒体が提供される。
【００２９】
本発明の第４の態様によれば、コンピュータ上に読み込まれたときに、コンピュータに本発明の第２の態様のコンピュータシステムを提供させる命令を含む機械読み取り可能媒体が提供される。
【００３０】
本発明の第５の態様によれば、動的確率計画法問題を解くように構成されたプログラムが提供され、該プログラムは、問題を反復的に解くことができる構成要素のスイートを提供し、該構成要素はジェネレータモジュール、ソルバーモジュール、シミュレーションモジュール、及び可視化モジュールを備え、
ｉ．ジェネレータモジュールは、モデル入力から動的確率計画（ＤＳＰ）を生成し、シミュレーションモジュールの出力を変換してソルバーモジュールによって処理するように構成され、
ｉｉ．ソルバーモジュールは、ＤＳＰを処理するように構成され、
ｉｉｉ．シミュレーションモジュールは、ジェネレータモジュールによって処理するための確率的プロセスをシミュレートするように構成され、
ｉｖ．可視化モジュールは、入力の出力とソルバーモジュールによって生成された結果とを提供する。
【００３１】
本発明の第６の態様によれば、本発明の第５の態様のプログラムを提供する命令を含む機械読み取り可能媒体が提供される。
【００３２】
本発明の態様のいずれかの機械読み取り可能媒体は、以下の非網羅的リスト：すなわち、フロッピーディスク、ＣＤ  ＲＯＭ／ＲＡＭ、ＤＶＤ  ＲＯＭ／ＲＡＭ（−Ｒ／−ＲＷ及び＋Ｒ／＋ＲＷを含む）、ハードドライブ、メモリ、任意の形態の磁気及び光学ディスク、送信信号（インターネットダウンロード、ｅメール、ｆｔｐ、又は同様のものを含む）、ワイヤのいずれかとすることができる。
【発明を実施するための最良の形態】
【００３３】
次に、例証として、添付図面を参照しながら本発明の詳細な説明に移る。
【００３４】
図１に示されたコンピュータシステム１００は、この場合はＬＣＤ（液晶ディスプレイ）モニタであるディスプレイ手段１０２、キーボード１０４、マウス１０６、及び処理回路１０８を備える。ＬＥＰ（発光ポリマー）、ＣＲＴ（陰極線管）ディスプレイ、プロジェクタ、テレビ、及び同様のものなどの他のディスプレイ手段も同様に利用可能とすることができる点は理解されるであろう。
【００３５】
処理回路１０８は、処理手段１１０、ハードドライブ１１２（格納データを含む）、メモリ１１４（ＲＡＭ及びＲＯＭ）、Ｉ／Ｏサブシステム１１６、及びディスプレイドライバ１１７を備え、これらは全て当該技術分野で知られるように、システムバス１１８を介して相互に通信する。処理手段１１０は通常、少なくとも１つのＩＮＴＥＬ（商標）ＰＥＮＴＩＵＭ（商標）シリーズプロセッサ（勿論他のプロセッサを使用することも可能）を含み、データの計算を実行する。他のプロセッサは、ＡＭＤ（商標）ＡＴＨＬＯＮ（商標）、ＰＯＷＥＲＰＣ（商標）、ＤＩＧＩＴＡＬ（商標）ＡＬＰＨＡ（商標）などのプロセッサを含むことができる。
【００３６】
ハードドライブは、プログラム及び他のデータ用の大容量記憶手段として使用される。メモリ１１４は、以下に詳細に説明する。
【００３７】
キーボード１０４及びマウス１０６は、処理手段１１０への入力手段を提供する。ＣＤ  ＲＯＭ、ＤＶＤ  ＲＯＭ、スキャナ、他のような他の装置をシステムバス１１８に結合し、データの格納、ネットワーク上での他のコンピュータとの通信、その他を可能にすることができる。こうしたいずれの装置も追加の入力手段を含むことができる。
【００３８】
Ｉ／Ｏ（入力／出力）サブシステム１１６は、キーボード１０４から、及び処理手段１１０から入力を受け取るように構成され、他の外部装置及び／又は内部装置からの通信を可能にすることができる。ディスプレイドライバ１１７により、処理手段１１０がディスプレイ１０２上に情報を表示できるようになる。
【００３９】
処理回路１０８は更に送信／受信手段１２０を備え、処理回路１０８がネットワークと通信することができるように構成されている。送信／受信手段１２０はまた、バス１１８を介して処理回路１０８と通信する。
【００４０】
処理回路１０８は、本来はＩＢＭ（商標）仕様に基づくＰＣとして知られるアーキテクチャを有することができるが、同様に他のアーキテクチャを有することもできる。処理回路１０８は、ＡＰＰＬＥ（商標）であってもよく、又はＲＩＳＣシステムとすることができ、種々のオペレーティングシステム（場合によっては、ＨＰ−ＵＸ、ＬＩＮＵＸ、ＵＮＩＸ、ＭＩＣＲＯＳＯＦＴ（商標）ＮＴ、又はＡＩＸ（商標）、又は同様のもの）を実行させることができる。処理回路１０８はまた、個人用デジタル情報端末（ＰＤＡ）、メインフレーム、電話、テレビ、腕時計、又は同様のものなどの装置によって提供することもできる。
【００４１】
メモリ１１４について述べているが、該メモリは種々の装置によって提供することができる点は理解されるであろう。例えば、メモリは、キャッシュメモリ、ＲＡＭメモリ、ハードディスク１１２などのローカルの大容量記憶装置、送信／受信手段１２０を介したようなネットワーク接続上で処理回路１０８に接続されたこれらのいずれかにより提供することができる。しかしながら、処理手段１１０は、システムバス１１８を介してメモリにアクセスし、どの段階を実行するかを命令し、更にデータサンプルにアクセスするためのプログラムコードにアクセスすることができる。次いで、処理手段１１０は、プログラムコードによってアウトラインされるデータサンプルを処理する。
【００４２】
メモリ１１４は、プログラムコードなどの実行中の命令を保持するために使用され、プログラムストレージに割り当てられたプログラムストレージ部分１５０を含む。プログラムストレージ部分１５０は、処理手段１１０に予め定められた動作を実行させるのに用いることができるプログラムコードを保持するのに使用される。
【００４３】
メモリ１１４はまた、保持データに割り当てられたデータストレージ部分１５２を含み、本発明の実施形態では特に、ＤＳＰモデル１５４及びシナリオツリー１６４を保持する。
【００４４】
図１のコンピュータシステム１００は、全体的に動的確率計画（ＤＳＰ）を作り且つ解くことができる構成要素２００のスイートを提供するように構成される。この実施形態では、以下に説明されるように互いに相互作用する５つの構成要素があるが、他の実施形態では、より多くの又はより少ない構成要素であってもよい。構成要素はまた、コンピュータシステム上で動作しているプログラム内部のモジュールと考えることもできる。
【００４５】
構成要素のどれもがＤＳＰの許容可能な解を求める全体プロセスで利用される。しかしながら、特定のアプリケーションに対するスイートをカスタマイズするために、構成要素の一部の調整可変部を必要とする場合がある。構成要素は、以下で説明される。
【００４６】
ロバストな解を求めることは、一般に、計画問題の改良、シミュレーション及び最適化の再実行、及び結果の解釈のインタラクティブプロセスを含む。このプロセスを次に説明する。現在及び将来において不確実性を伴う計画問題を考慮する際には、発明者らの現在の決定は現在認識していることに基づいているだけであるので、発明者らの計画問題はほぼマルコフ過程であると考えるのが有用であることは理解されるであろう。更に、将来シナリオの発明者らの予測は、一度に一回だけのステージでツリーのように外側に向かって分岐する。このノード作成は、分解ソルバーを特に効率的にする。非予想制約での単層シナリオ構造用に汎用ソルバーを使用する幾つかの他の手法よりも遙かに効率的である。
【００４７】
構成要素の説明
ジェネレータ構成要素２０２は、スイート２００の中心構成要素であり、専用プログラム言語で書かれたモデルからＤＳＰを生成する。これは、テキストファイルで保存されたプログラムを読み取り、これを特定のシナリオ構造体と組み合わせて、スイート２００のソルバー構成要素２０４によって解くことのできるＤＥＰの内部表現を生成するコンパイラと考えられる。特定のシナリオ構造体は、メモリ１１２、１１４内部に保持されたシナリオツリー１６４によって定められる。
【００４８】
ＤＳＰは、ツリーの各ノードが決定ポイントを表すツリーとして表現され、この決定ポイントで、別の将来シナリオの観点で将来を評価する必要がある。このツリーは、シナリオツリーと呼ぶことができ、シミュレートされたシナリオは、ツリーを通る１つの特定経路を表し、従って、１つの特定の将来予想を表す。多くのシナリオ（すなわちツリーを通る経路）が同じ分岐及びノードを含み、従ってシナリオに冗長性が存在することになる点は理解されるであろう。本発明の幾つかの実施形態は、この冗長性を利用し、代替シナリオが評価されるときにシナリオの諸々の部分を再評価する必要がないようにするために、評価されるシナリオの部分を記憶することができる。
【００４９】
ジェネレータ構成要素２０２の第２の機能は、シミュレータ構成要素２０６によって生成されたシナリオを解法プロセスの間にソルバー構成要素２０４によって必要とされる構造体に読み込むことである。これは、ソルバー構成要素２０４内の複数のソルバーの内の１つで具現化される分割法を利用する、シナリオのノード作成のノード毎の動的プロセスとすることができる。本発明の幾つかの実施形態は、幾つかのソルバーを連続して利用することができる。この手段により、同時に処理するには大きすぎる計画問題は、管理可能なサブタスクに分解することができる。
【００５０】
スイートの第２の構成要素は、ソルバー構成要素２０６であり、現実世界のＤＳＰの特定の特徴を利用するように設計された幾つかの分解ソルバーを含む。これらの特徴は、上述されたように将来において不確実性が展開する方法を反映する。
【００５１】
通常あらゆるアプリケーションにおいても、将来の代替シナリオで予測すべき幾つかのプロセス及びイベントがある。シミュレーション構成要素２０６は、株式、債券、金利、キャッシュフロー、生産、及びインフレーションなどの金融及び経済プロセス用にシミュレータのセットを含む。本実施形態では、資産シミュレータ１６６と債務シミュレータ１６８が提供される。エネルギー、石油、又は遠距離通信用帯域幅に対する供給と需要などの現実世界のプロセス用のシミュレータがある。更に、個人の疾病及び死亡などの現実世界のイベント用のシミュレータもある。これらは、目前の特定の計画問題に対して必要とされるプロセス及びイベントの全てをシミュレートするのに使用され、或いはシミュレートするよう適合することができる。
【００５２】
モデル化プロセス全体を通じて、入力データとソルバー結果を検査し、シナリオ構造体を改良することにより解のロバスト性を向上させることが望ましい。これは、シミュレートされたシナリオ及びソルバーによって求められた条件付き決定は膨大な量の数値データを含むことが多いので、これらのグラフィック表現が無いと困難な可能性がある。可視化構成要素２０８は、このようなツールを提供する。
【００５３】
可視化構成要素２０８は、シナリオツリー及びソルバー結果についてのグラフィカルビューワの選択からなる。これらは、詳細部分に埋もれることなく、シナリオの全体形状及びフローを実行者が見ることができる方法で、シナリオの大きな分布を表示することができる。これは、反復モデル化プロセスの正常な制御に有利である。
【００５４】
スイート２００の柔軟性及びカスタマイズ機能は、ライブラリ構成要素２１０、すなわち、モデル及びシナリオ及び解を生成・編集・処理・閲覧するルーチンの包括的ライブラリによって提供される。このライブラリでは、他の構成要素（シミュレーション構成要素２０６、ジェネレータ構成要素２０２、ソルバー構成要素２０４、及び可視化構成要素２０８）をカスタマイズし、金融ポートフォリオ管理又は資産及びライブラリ管理などの特定のアプリケーションに適合させることが可能である。ライブラリ構成要素２１０は、ＤＳＰに特有の他のルーチンのツールキットばかりでなく、これらの他の構成要素の機能性の多くにアプリケーションプログラミングインターフェース（ＡＰＩ）を提供する。
【００５５】
図３を参照すると、スイート２００の種々の構成要素が以下で概説される手続き呼び出し及びデータ構造により通信することが分かる。
【００５６】
ジェネレータ構成要素２０２は、メモリ１１２、１１４からＤＳＰモデル１５４を読み込み、これをＤＥＰ中にコンパイルしてシナリオデータと組み合わせ、ソルバー構成要素２０４にプログラムを渡すように構成されたモデルコンパイラ３００を含む。この実施形態では、ソルバー構成要素は、ネストされたベンダーソルバー１５６を含む。ネストされたベンダーソルバー１５６は、集約ヒューリスティックスを使用して問題を分解し、次いで、ネストされたベンダーアルゴリズムの適応により区分的に問題を解く。
【００５７】
ＤＥＰの内部構造は、可視化構成要素２０８によって検査することができる。詳細には、可視化構成要素は、効率的解法のためのプログラムの最適な形態を決定するために構造体ビューワ１５８を含む。計画問題が解けると、解はモデルコンパイラ３００に戻され、そこで可視化構成要素２０８によって提供された解ビューワ１６０を使用してこれを検査することができる。
【００５８】
モデルコンパイラ３００は、必要であれば、適切なソルバーインターフェスを用いてソルバー構成要素２０４以外のソルバーが読み取ることができるテキストファイルの形態でＤＥＰを生成することができる。柔軟ではあるが、上述の理由から、これは制約的で非効率的である。
【００５９】
モデルコンパイラ３００は、ソルバー構成要素２０４によって必要とされたシナリオツリー１６４の各区分についての経路／ツリージェネレータ１６２を呼び出す。経路／ツリージェネレータ１６２は、シミュレーション構成要素２０６によって提供されるシミュレータ１６６、１６８を順に反復的に呼び出し、要求された経路又はツリーの各ノードを埋める。
【００６０】
経路／ツリージェネレータ１６２は、必要であれば、解くのと同時にジェネレータ構成要素２０２によって提供される、ツリーウオーカー１７０が読み込むことができる深さ優先先行順のデータファイルとして全体のシナリオツリー１６４を生成することができる。このシナリオツリー１６４は、可視化構成要素２０８によって提供されたツリービューワ１７２で表示することができる。
【００６１】
図４は、図１から図３に示されたスイートの使用を概説するフローチャートである。この図は、計画問題に対してロバストな解を作成するためにスイートの実施形態の反復的な利用をどのように用いることができるかを示している。図では、プロセスは、確率的プロセスの推定から始まる。
【００６２】
ステップ１（４００）
実行者は、実行者の予測に関連する不確実性又はリスクの特性を解析することによって計画プロセスを開始する。（明らかに、将来が確実性を有することが分かっている場合には、計画は完全に決定論的であり、問題は自明である）。通常、これは、例えば、株式及び債券の価格、又は個人の寿命及びケアの必要性などの幾つかの確率的プロセスの推定を含む。他の実施例では、確率的プロセスは、エネルギー、石油、又は遠距離通信用帯域幅に対する供給と需要などの現実世界のプロセスに対するシミュレータとすることができ、これは設備及び工場の設計に使用することができる。リアリズムに関しては、これらのモデルは、一般に履歴データサンプルに基づく。このタスクを支持することが可能な様々な高度統計ツールが既に存在する。
【００６３】
ステップ２（４０２）
次のステップは、モデル化言語を使用してＤＳＰを作成することである。上述のように、これは、生成されることになるシナリオ構造体とは関係なく、決定論的な数理的形態で問題を記述することにより最も好都合且つ一意的に行われる。これは、どのパラメータが固定され、どのパラメータがランダムであるかを識別するには十分である。勿論、決定変数はランダムであり、実行者が指定する制約及び目的に依存する。
【００６４】
これらの制約は、経時的に一貫して当てはまり、シナリオ構造体の特定の選択には関係しない。例えば、非予想制約を除外するこの明らかな柔軟性の損失は、スイートを使用するＤＳＰが好適な現実世界の問題の特性に完全に一貫している。この主な利点は、あらゆる他の確率計画法（ＳＰ）手法とは異なり、様々なシナリオ構造体によって変わる必要のない計画問題をコンパクトに表現できることである。
【００６５】
ステップ３（４０４）
ＤＳＰが作成されると、実行者は、改良されている間にシミュレーション構成要素２０６を使用してジェネレータ構成要素２０２が必要とするシナリオをシミュレートし、ＤＳＰをＤＥＰの中にコンパイルする。この実施形態では、資産１６６及び債務１６８のシミュレータは、ステップ１（図中の４００）で推定されたパラメータを用いてロードされる。株式及び債券などの資産、金利及び為替レートなどの財務要因、生産及びインフレーションなどの経済的要因、ローン、抵当及びキャッシュフローなどの債務、及び疾病又は死亡などの個人のイベント、並びに他の技術及び業務関連の着想のためのシミュレーション構成要素２０６に複数のシミュレータがあることは理解される。
【００６６】
シナリオは、ソルバー構成要素２０４を動作させながら、ジェネレータ構成要素２０２による要求に応じて個々に生成し、或いはその後でソルバーのツリーウオーカー１７０によって「移動された」（サブ）ツリーとして予め計算される。実行者は、モデル化を反復する毎に必要とされる時間ステップ及び分岐構造体を指定する。通常、僅かな時間ステップと低分岐ファクタを有する短いツリーから始まる。しかしながら、モデル１５４が改良されるので、解を改良してそのロバスト性を証明するために、時間ステップ及び分岐の数が増大し、場合によっては非対称のツリーを生成することもある。これはＤＳＰの変更を必要とせずに行われる。
【００６７】
実際に、図４に示されたフィードバックループ（順次サンプリングフィードバックループ４０６、適応性フィルタリングフィードバックループ４０８、及び較正フィードバックループ４１０）を用いて、構成要素２００のスイートが半自動で反復的にシナリオ構造体を改良することが可能である。順次サンプリングフィードバックループ４０６によって提供される順次サンプリングは、ソルバーからの完全な情報の期待値に基づく順次重要度サンプリングから得られたデータを使用して、追加のサンプリングを必要とする領域でだけシナリオツリーを成長させ、この結果冗長性入力データを回避して効率を維持する方法である。適応フィルタリングによって、システムは基礎データからモデルを自動的に更新することができる。
【００６８】
較正フィードバックループ４１０は、ＤＳＰで使用された係数が期待を上回って変わっているかどうかを判断する。そうである場合、ＤＳＰは、この期待を上回る変化を低減するように調整することができる。
【００６９】
ステップ４（４１２）
ＤＳＰ及びシナリオ構造体適切であれば、実行者は、ジェネレータ構成要素２０２を動作させてモデルを「コンパイル」する。ジェネレータ構成要素２０２は、ＤＳＰをバッチモードでコンパイルし動作させることができ、又はプログラミング言語を端末セッションでインタラクティブに解釈することができる。インタプリタとして、正しいシンタックスでユーザを支援するためにフィードバックを提供するだけでなく、ユーザがソルバー構成要素２０４を反復的に実行することが可能となるので、ユーザは、ソルバー構成要素２０４からの結果に基づいて（又は結果が無くとも）ＤＳＰを修正し拡張することができる。
【００７０】
このインタラクティブなモードは、高度なＤＳＰの迅速なプロトタイピング及び開発に有用である。サードパーティの数理プログラミング言語の他の確率計画法の拡張は、本発明の実施形態により使用されるプログラミング言語とは異なり、これらの拡張をコンパイルする際の前処理段階に依存することに留意されたい。これは、この拡張は、このインタラクティブな解釈能力はないが、冗長なバッチモードでだけ使用することができることを意味している。
【００７１】
更に、本発明の実施形態により使用されるプログラミング言語は、ソルバー構成要素２０４から結果を読み取り、シナリオの一部又は全てにわたる期待値及び分布などの解に関する統計的情報を記録することができる特定の抽出、表示、及び印刷コマンドを有する。この能力は、他のシステムには組み込まれず、シナリオがハードコードされる必要があるが、この特徴を提供する本発明の実施形態には好都合である。
【００７２】
ステップ５（４１４）
ユーザは、他のいずれかの数理プログラミング言語を使用するのと同様に「解」コマンドを使用してインタラクティブに又はバッチモードでソルバー構成要素２０４を呼び出す。他のあらゆる確率計画法の拡張とは異なり、ジェネレータ構成要素２０２は、ソルバー構成要素２０４を直接呼び出し、ソルバー構成要素２０４の内部データ構造体と読み書きを行う。この特徴が提供される実施形態では、システムの応答性が全体的に増大する。ＤＥＰのテキスト表現を別のプロセスに渡してコンパイルし動作する他の確率的システムには、この利点はない。
【００７３】
ソルバーは、ＤＳＰ及びシナリオツリーからコンパイルされた、ＤＥＰに対する最適解を計算する（勿論、制約セットにより問題が実現不能でない限り）。上述のように、ソルバー構成要素２０４は、現実世界の問題に対する解を他の汎用ソルバーよりも１０倍〜１００倍速く計算することができる。この最適解は、シミュレーション構成要素２０６によって提供されたシミュレータが生成する特定のシナリオセットに多少なりとも依存するので、かえって好都合である。異なるサンプルセットは、多少は異なる解を生成するであろう。差が有意であるかどうかは、後続の解析に左右される。
【００７４】
通常、実行者は、構成要素２００のスイートを使用し、シナリオ構造体を反復的に修正して、問題を解くのに要する時間と解の精度の平衡をとることになる。平衡がとれると、多くの異なるシナリオのサンプルでモデルの動作を始め、得られる結果の分散を設定する。この点で動的確率計画法は、決定的計画法とは異なり、すなわち最初から正しく動作するのではなく、高度に反復的なプロセスである。
【００７５】
ステップ６（４１６）
モデルの各反復において、実行者は、そのリアリズムに対してソルバーの解を評価することができる。解が極めて多くの数の個々の前方決定（シナリオツリーの各ノードにおける変数）を含むことができるとすると、形状の印象と解のフローと目的に対する適合性を得ることが重要である。これは、入力シナリオ（ツリー及びその分岐）を結果として得られた解（平均及び分布で）と比較する段階を伴う。連続変数を有する決定ツリーの等価物として解を捉えることができる。用語「前方決定」とは、将来における時間のポイントで評価すべき決定として使用されている。
【００７６】
これは、ソルバー構成要素２０４から数値的ではなく可視化構成要素２０８で可視的に良好に行うことができる。ソルバー構成要素２０４ではなく可視化構成要素２０８が使用される実施形態の利点は、異常及び矛盾及び欠陥のある決定ロジック、不適切な異常値などをユーザが迅速に突き止めることができることである。次いで、これらは、データまで掘り下げて問題を診断し、プログラム又はシナリオ構造体のいずれかを補正することができる。問題がシミュレーションにある場合、これらは、モデルのこれまでの反復からのフィードバックにより再較正することができる。
【００７７】
恐らくは、過去において確率的プログラムは非現実的なほど小さかったので、他のシステムはグラフィカルツールを統合していなかった。これまでの手法は、サードパーティのグラフィックパッケージを場合によっては利用していたが、モデル化プロセスの統合部分としてではなく、特定の問題のある態様を示すアドホックのものに過ぎない。構成要素２００のスイートの統合された可視化構成要素２０８は、ＤＳＰの分野では一意的である。
【００７８】
本発明を提供するのに好適な構成要素２００のスイートの実施例は、Ｅａｒｌ  Ｓｔｒｅｅｔ，  Ｃａｍｂｒｉｄｇｅ，  ＣＢ１  １ＪＲのＣａｍｂｒｉｄｇｅ  Ｓｙｓｔｅｍ  Ａｓｓｏｃｉａｔｅｓ  Ｌｔｄ．によって提供される。この特定のスイートでは、ジェネレータ構成要素２０２はＳｔｏｃｈＧｅｎ（商標）と呼ばれ、シミュレーション構成要素２０６はＳｔｏｃｈＳｉｍ（商標）、可視化構成要素２０８はＳｔｏｃｈＶｉｅｗ（商標）、ライブラリ構成要素２１０はＳｔｏｃｈＬｉｂ（商標）と呼ばれる。
【００７９】
ＤＳＰの実施例
【数１−１】
2008501171.tif 000003
【数１−２】
2008501171.tif 000004
【数１−３】
2008501171.tif 000005
【数１−４】
2008501171.tif 000006
【数１−５】
2008501171.tif 000007
【数１−６】
2008501171.tif 000008
【数１−７】
2008501171.tif 000009
【数１−８】
2008501171.tif 000010
【図面の簡単な説明】
【００８０】
【図１】本発明の一実施形態を実現するために好適なコンピュータシステムの概略図である。
【図２】本発明の一実施形態の構成要素の概要の概略図である。
【図３】構成要素内のユニットがどのように互いに通信するかを示す概略図である。
【図４】図１及び図２に示された本発明の使用法を概説する図である。
【符号の説明】
【００８１】
２００  スイート
２０２  ジェネレータ構成要素
２０４  ソルバー構成要素
２０６  シミュレーション構成要素
２０８  可視化構成要素
２１０  ライブラリ構成要素
【図１】
2008501171.tif 000011
【図２】
2008501171.tif 000012
【図３】
2008501171.tif 000013
【図４】
2008501171.tif 000014
【国際調査報告】
2008501171.tif 000015
2008501171.tif 000016
2008501171.tif 000017
2008501171.tif 000018