(57)【要約】【課題】コンピュータ化された多重制約問題空間における最適化解を選択するための方法、システム、およびコンピュータ・プログラム製品を提供する。【解決手段】本方法は、最適化のための線形関数を受信するステップと、該線形関数に対する制約のセットを受信するステップと、線形計画ソルバを用いて線形関数および初期制約に対する第一最適解を算定するステップと、初期制約と併せ第一最適解を制約として用いて、制約の新規セットを生成するステップと、線形関数にスラック変数の二次目的を加えることによって、新規二次関数を生成するステップと、二次計画ソルバを用いて二次関数および新規制約に対する解を算定するステップと、を含む。【選択図】図３
2015501057.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータ化された多重制約問題空間における最適化解を選択するための方法であって、前記方法は、
最適化のための線形関数を受信するステップと、
前記線形関数に対する制約のセットを受信するステップと、
線形計画ソルバを用いて前記線形関数および初期制約に対する第一最適解を算定するステップと、
前記初期制約と併せ前記第一最適解を制約として用いて、制約の新規セットを生成するステップと、
前記線形関数にスラック変数の二次目的を加えることによって、新規二次関数を生成するステップと、
二次計画ソルバを用いて前記二次関数および新規制約に対する解を算定するステップと、
を含む、方法。
【請求項２】
前記スラック変数制約が重み付けのデフォルト・セットを有する、請求項１に記載の方法。
【請求項３】
前記スラック変数制約は、管理者またはユーザが決定した一つ以上の費用係数に基づいている、請求項２に記載の方法。
【請求項４】
前記線形関数は整数関数とすることが可能な、請求項１〜３のいずれかに記載の方法。
【請求項５】
請求項１に記載の方法を使ってデバイスを制御する方法。
【請求項６】
コンピュータ化された多重制約問題空間において一つ以上の最適化された値を選択するための方法であって、前記方法は、
混合整数計画コンポーネントの入力値の第一セット、線形計画コンポーネントの入力値の第二セット、およびユーザが決定した一つ以上の費用係数に基づく、平方スラック変数制約の費用重み付けされたセットを入力として受信するステップと、
前記混合整数計画コンポーネントの出力値の第一セットを生成するステップと、
前記線形計画コンポーネントの出力値の第二セットを生成するステップと、
前記出力値の第一セットおよび前記出力値の第二セットに従って制限解空間を生成するステップと、
前記ユーザが決定した一つ以上の費用係数に基づく前記平方スラック変数制約の費用重み付けされたセットに基づいて、さらなる制限を適用することによって、前記制限解空間から最適化された値を選択するステップと、
を含む、方法。
【請求項７】
コンピュータ化された多重制約問題空間における最適化解を選択するためのシステムであって、前記システムは、
最適化のための線形関数を受信するための手段と、
前記線形関数に対する制約のセットを受信するための手段と、
線形計画ソルバを用いて前記線形関数および初期制約に対する第一最適解を算定するための線形ソルバと、
前記初期制約と併せ前記第一最適解を制約として用いて、制約の新規セットを生成するための手段と、
前記線形関数にスラック変数の二次目的を加えることによって、新規二次関数を生成するための手段と、
二次計画ソルバを用いて前記二次関数および新規制約に対する解を算定するための二次ソルバと、
を含む、システム。
【請求項８】
前記スラック変数制約が重み付けのデフォルト・セットを有する、請求項７に記載のシステム。
【請求項９】
スラック変数制約は、管理者またはユーザが決定した一つ以上の費用係数に基づいている、請求項８に記載のシステム。
【請求項１０】
前記線形関数は整数関数とすることが可能な、請求項７〜９のいずれかに記載のシステム。
【請求項１１】
請求項１〜５のいずれかに記載の方法を用いるデバイスを制御するためのコントローラ。
【請求項１２】
コンピュータ化された多重制約問題空間における最適化解を選択するためのコンピュータ可読コードが格納されたコンピュータ可読記録媒体を含む、コンピュータ・プログラム製品であって、前記コンピュータ可読コードは、コンピュータ・システムにロードされ実行されたとき、
最適化のための線形関数を受信するステップと、
前記線形関数に対する制約のセットを受信するステップと、
線形計画ソルバを用いて前記線形関数および初期制約に対する第一最適解を算定するステップと、
前記初期制約と併せ前記第一最適解を制約として用いて、制約の新規セットを生成するステップと、
前記線形関数にスラック変数の二次目的を加えることによって、新規二次関数を生成するステップと、
二次計画ソルバを使って、前記二次関数および新規制約に対する解を算定するステップと、
を遂行する、コンピュータ・プログラム製品。
【請求項１３】
前記スラック変数制約が重み付けのデフォルト・セットを有する、請求項１２に記載のコンピュータ・プログラム製品。
【請求項１４】
前記スラック変数制約は、管理者またはユーザが決定した一つ以上の費用係数に基づいている、請求項１３に記載のコンピュータ・プログラム製品。
【請求項１５】
コンピュータ可読媒体に格納され、デジタル・コンピュータの内部メモリにロード可能なコンピュータ・プログラムであって、前記プログラムがコンピュータ上で実行されたとき、請求項１〜５のいずれかに記載の前記方法を遂行するためのソフトウェア・コード部分を含む、前記コンピュータ・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、最適解の混合のための方法および装置に関する。具体的には、本発明は、実用的な最適解を迅速に見出すための、最適解の混合のための方法および装置に関する。
【背景技術】
【０００２】
線形計画法（ＬＰ：Ｌｉｎｅａｒ  ｐｒｏｇｒａｍｍｉｎｇ）および混合整数計画法（ＭＩＰ：ｍｉｘｅｄ  ｉｎｔｅｇｅｒ  ｐｒｏｇｒａｍｍｉｎｇ）は、最適化アプリケーションを構築するための周知の技術である。最適化問題は、線型方程式（ＬＰ）を用いて、時には整数値決定変数（ＭＩＰ）を用いて近似計算される。このとき、モデル（一組の方程式）が、ＩＢＭ（登録商標）  ＩＬＯＧ（登録商標）  ＣＰＬＥＸ（登録商標）のようなＬＰまたはＭＩＰエンジンによって解かれ、ある目的に関する最適解（またはＭＩＰの場合は近似最適解）が出力される。ＩＢＭ、ＣＰＬＥＸおよびＩＬＯＧは米国その他の国におけるインターナショナル・ビジネス・マシーンズ・コーポレーションの商標である。
【０００３】
最適化エンジン（例えばＬＰおよびＭＩＰエンジン）は、それが数学的に最適である場合でさえも、望ましくない特性を有する解を提供することがある。また、ある解決エンジンによって提示される解は、全ての可能な解からそのエンジンの自己判断で選択される。一般に、解は、解決対象の問題のセマンティクスに関係なく、アルゴリズムの基準または数学的基準に基づいて選択される。さらに、ＬＰの場合、およびＭＩＰの場合もより程度は少ないが、解は、一般に極値（数学的には、数学的探索空間中の頂点）である、すなわち、ＬＰ/ＭＩＰアルゴリズムは、決定変数の非常に小さなサブセットを使ったソリューションを選好する。一部の変数は、それらの値がゼロの場合「人為的に使用されない」が、正値を有すれば解の質が低下することはなく、数学的にこれらは「基底内だが空値」である。
【０００４】
従来技術は、既知の解の混合の問題に取り組んでいるが、実行可能または最適空間の中ほどで解を発見し、極値解の代わりに妥協解の計算を可能にするアプローチはしていない。
【０００５】
一つの単純なソリューションは、全ての極値解Ｓ１、Ｓ２、・・・Ｓｎを探索し、重み付き解の和を重みで除算することである。
【０００６】
この単純な解法は、平均計算の中に極値解の全てが含まれるという不利点がある。これらの全ての解は、明示的に計算する必要があり、非常に時間/ＣＰＵ消費的である。極値解は、頂点または基底解としても知られる。また、潜在的に数多くの極値解があるので、それらを計算するにはいくらか時間を要する。
【０００７】
パレート最適を用いた別のソリューションも、解Ｓ１、Ｓ２、・・・Ｓｎの全てを用いる。このソリューションは、関連する個別の解の明示的（既知の）リストを使い、より洗練されたやり方でバランスを取って解を計算する。これは、計算時間をいくらか節減できるが、関連する個別の解のリストが既に分かっている必要がある。
【０００８】
背景となる従来技術を説明する。
【０００９】
特許文献１（名称「Ｍｅｔｈｏｄ  ｆｏｒ  ｏｐｔｉｍｉｚｉｎｇ  ａ  ｔｒａｎｓｆｏｒｍａｔｉｏｎ  ｓｃｈｅｍｅ」）は、複数の目的の包含を開示しているが、複数の最適解の混合は開示していない。
【００１０】
特許文献２（名称「Ｍｅｔｈｏｄ  ａｎｄ  ｓｙｓｔｅｍ  ｆｏｒ  ｓｏｌｖｉｎｇ  ｓｔｏｃｈａｓｔｉｃ  ｌｉｎｅａｒ  ｐｒｏｇｒａｍｓ  ｗｉｔｈ  ｔｈｅ  ｃｏｎｄｉｔｉｏｎ  ｖａｌｕｅ  ａｔ  ｒｉｓｋ  ｃｏｎｓｔｒａｉｎｔs」）の確率論的なＭＩＰ法は、リスク拘束に関して、最適性を反復法で探索しているが、最適解の混合はしていない。
【００１１】
特許文献３（名称「Ｌｉｎｅａｒ  ｐｒｏｇｒａｍｍｉｎｇ  ｒｅｌａｘａｔｉｏｎ  ｍｏｄｉｆｉｃａｔｉｏｎ  ａｎｄ  ｃｕｔ  ｓｅｌｅｃｔｉｏｎ  ｉｎ  ａ  ＭＩＰ  ｓｏｌｕｔｉｏｎ」）は、探索空間を刈り込むためにＬＰ緩和法および切断面を用いているが、最適解の混合はしていない。
【００１２】
特許文献４（名称「Ｉｎｔｅｇｒａｔｅｄ  ｄｅｃｉｓｉｏｎ  ｓｕｐｐｏｒｔ  ｓｙｓｔｅｍ  ｆｏｒ  ｏｐｔｉｍｉｚｉｎｇ  ｔｈｅ  ｔｒａｉｎｉｎｇ  ａｎｄ  ｔｒａｎｓｉｔｉｏｎ  ｏｆ  ａｉｒｌｉｎｅ  ｐｉｌｏｔｓ」）では、適応的、動的、統合的、且つ自動化された最適化システムが、混合整数計画モデルの複数の代替解を提供するように変更された前記混合整数計画モデルのパラメータを含む。このモデルは、複数の解を提案しているが、各解は、モデルのパラメータ変更による相異なったＭＩＰモデル（唯一のモデルでない）の最適解である。さらに、これらの様々な解は混合されずに、そのままユーザに提示される。
【００１３】
特許文献５（名称「Ｍｉｘｅｄ  ｉｎｔｅｇｅｒ  ｐｒｏｇｒａｍｍｉｎｇ  ｍｏｄｅｌ  ｆｏｒ  ｍｉｎｉｍｉｚｉｎｇ  ｌｅａｓｅｄ  ａｃｃｅｓｓ  ｎｅｔｗｏｒｋ  ｃｏｓｔｓ」）は、ＭＩＰ問題の一つ（だけ）の解を見出すための、標準的ＭＩＰアルゴリズムのあるアプリケーションを開示している。新規性はモデルにあり、解法アプローチではない。これも、最適化ステップの後、解の混合はしていない。
【００１４】
特許文献６（名称「Ｓｈｉｐｐｉｎｇ  ａｎｄ  ｔｒａｎｓｐｏｒｔａｔｉｏｎ  ｏｐｔｉｍｉｚａｔｉｏｎ  ｓｙｓｔｅｍ  ａｎｄ  ｍｅｔｈｏｄ」）では、ＭＩＰモデルが一連のＬＰとその後の局部的探索によって解かれる。両方のケースでの一連の解は最適でなく（その上、混合されていず）、アルゴリズムは、最初の解で停止基準を満たして停止する。
【００１５】
特許文献７（名称「Ｏｐｔｉｍｉｚｉｎｇ  ｓｗｉｔｃｈ  ｐｏｒｔ  ａｓｓｉｇｎｍｅｎｔｓ」）は、１）伝統的なＱＰｗ/ａ分枝限定法、２）二次項のＩＰ近似の２つの方法によって解かれる二次ＭＩＰモデルである。この公報中には、最適解の混合はない。
【先行技術文献】
【特許文献】
【００１６】
【特許文献１】米国特許出願公開第２０１０／０２８７０７３（Ａ１）号（名称「Ｍｅｔｈｏｄ  ｆｏｒ  ｏｐｔｉｍｉｚｉｎｇ  ａ  ｔｒａｎｓｆｏｒｍａｔｉｏｎ  ｓｃｈｅｍｅ」）
【特許文献２】米国特許出願公開第２００９／０２７１２３０（Ａ１）号（名称「Ｍｅｔｈｏｄ  ａｎｄ  ｓｙｓｔｅｍ  ｆｏｒ  ｓｏｌｖｉｎｇ  ｓｔｏｃｈａｓｔｉｃ  ｌｉｎｅａｒ  ｐｒｏｇｒａｍｓ  ｗｉｔｈ  ｔｈｅ  ｃｏｎｄｉｔｉｏｎ  ｖａｌｕｅ  ａｔ  ｒｉｓｋ  ｃｏｎｓｔｒａｉｎｔs」）
【特許文献３】米国特許出願公開第２０１１／０１３１１６７（Ａ１）号（名称「Ｌｉｎｅａｒ  ｐｒｏｇｒａｍｍｉｎｇ  ｒｅｌａｘａｔｉｏｎ  ｍｏｄｉｆｉｃａｔｉｏｎ  ａｎｄ  ｃｕｔ  ｓｅｌｅｃｔｉｏｎ  ｉｎ  ａ  ＭＩＰ  ｓｏｌｕｔｉｏｎ」）
【特許文献４】米国特許第７３４６５２８（Ｂ２）号（名称「Ｉｎｔｅｇｒａｔｅｄ  ｄｅｃｉｓｉｏｎ  ｓｕｐｐｏｒｔ  ｓｙｓｔｅｍ  ｆｏｒ  ｏｐｔｉｍｉｚｉｎｇ  ｔｈｅ  ｔｒａｉｎｉｎｇ  ａｎｄ  ｔｒａｎｓｉｔｉｏｎ  ｏｆ  ａｉｒｌｉｎｅ  ｐｉｌｏｔｓ」）
【特許文献５】米国特許出願公開第２０１１／０２０２６３８（Ａ１）号（名称「Ｍｉｘｅｄ  ｉｎｔｅｇｅｒ  ｐｒｏｇｒａｍｍｉｎｇ  ｍｏｄｅｌ  ｆｏｒ  ｍｉｎｉｍｉｚｉｎｇ  ｌｅａｓｅｄ  ａｃｃｅｓｓ  ｎｅｔｗｏｒｋ  ｃｏｓｔｓ」）
【特許文献６】米国特許出願公開第２００２／０１５６６６３（Ａ１）号（名称「Ｓｈｉｐｐｉｎｇ  ａｎｄ  ｔｒａｎｓｐｏｒｔａｔｉｏｎ  ｏｐｔｉｍｉｚａｔｉｏｎ  ｓｙｓｔｅｍ  ａｎｄ  ｍｅｔｈｏｄ」）
【特許文献７】米国特許出願公開第２００５／０２６５３５９（Ａ１）号（名称「Ｏｐｔｉｍｉｚｉｎｇ  ｓｗｉｔｃｈ  ｐｏｒｔ  ａｓｓｉｇｎｍｅｎｔｓ」）
【発明の概要】
【発明が解決しようとする課題】
【００１７】
全極値解の明示的な計算を回避し、しかして、この探索空間中での非現実的な探索を回避するためのソリューションが求められている。
【００１８】
もっと処理時間の少ないソリューションが必要である。
【００１９】
極値解の外部からの知識を要求されないソリューションが必要である。
【課題を解決するための手段】
【００２０】
本発明の第一態様において、コンピュータ化された多重制約問題空間における最適化解を選択するための方法が提供され、該方法は、最適化のための線形関数を受信するステップと、該線形関数に対する制約のセットを受信するステップと、線形計画ソルバを用いて線形関数および初期制約に対する第一最適解を算定するステップと、初期制約と併せ第一最適解を制約として用いて、制約の新規セットを生成するステップと、線形関数にスラック変数の二次目的を加えることによって、新規二次関数を生成するステップと、二次計画ソルバを使って、該二次関数および新規制約に対する解を算定するステップと、を含む。
【００２１】
このソリューションは、標準的ＬＰ／ＭＩＰ極値解を汎用的な妥協解で置き換えるものである。本ソリューションは、個別の最適解を無視して均衡を見出すが、代わりに、最適空間の「中ほどで」解を見出すために制約への距離を用いる。最先端技術は、既知の解の混合の問題に取り組んでいるが、最適空間の中ほどで解を発見し、極値解の代わりに妥協解の計算を可能にするアプローチは試みられていない。
【００２２】
本ソリューションは、個別極値解の間の均衡を見出すために、それらの全てを個別に計算する必要がないので、現実的レベルの複雑さのアルゴリズムを提供する。目的が正の定符号である多項式の複雑さを有する、平明な二次計画を用いることができる。
【００２３】
本提案の方法およびシステムは一般的であって、汎用ＬＰ／ＭＩＰソルバの機能とすることも、あるいは、あるデバイスを制御するためのコントローラ中の専門ＬＰソルバとすることも可能である。
【００２４】
また、これは、開発者、管理者、またはユーザが、各制約に対する重み付けされた係数の任意のセットを入力することによって簡単にカスタム化できるようにすることが可能である。
【００２５】
この解は、それでも当初の問題に対し最適である。この均衡の目的は、パレート最適を保証するものでない。これは、極値（頂点）解に関してではなく、制約に関して何らかの均衡を保証する。一切の最適化問題に対する妥協解は、極値解よりもロバストである。というのは、最適空間の中ほどにあるのは、制約の変化に起因する極端な解のシフトの変化を最小限にするからである。出力された妥協解は、提示された二次費用に対してテストすることができる。
【００２６】
二次関数は、望まれる解の制約までの二次距離（いわゆる「スラック」変数）である。この距離は、問題の不等制約中のスラック変数に基づいている。
【００２７】
望ましくは、このスラック変数制約は、重み付けのデフォルト・セットを有する。スラック変数は重み付けされ次いで２乗され、最後に、最適化プロセスの第二フェーズの目的を取得するために加算される。スラック変数の入力費用は、考案を識別するための指標である。あるいは、スラック変数制約は、管理者またはユーザが決定した一つ以上の費用係数に基づいている。これは、固有で同次の測定単位（前に目的関数の中で使われたのと同じ測定単位）による全ての距離を組み合わせる、制約スラック（調整量）のユーザ付与の費用によって重み付けされる。この距離は、制約への近接の費用を評価するユーザ付与の係数を用い、しかして測定単位に関し同次の距離メトリクスを有することによって、意味的に有意にされる。
【００２８】
有利には、この線形関数は整数関数とすることができる。
【００２９】
本発明の第二態様によって、コンピュータ化された多重制約問題空間において一つ以上の最適化された値を選択するための方法が提供され、本方法は、混合整数計画コンポーネントの入力値の第一セット、線形計画コンポーネントの入力値の第二セット、およびユーザが決定した一つ以上の費用係数に基づく、平方されたスラック変数制約の費用重み付けされたセットを入力として受信するステップと、前記混合整数計画コンポーネントの出力値の第一セットを生成するステップと、前記線形計画コンポーネントの出力値の第二セットを生成するステップと、前記出力値の第一セットおよび前記出力値の第二セットに従って制限解空間を生成するステップと、ユーザが決定した一つ以上の費用係数に基づく前記平方スラック変数制約の費用重み付けされたセットに基づいて、さらなる制限を適用することによって、前記制限解空間から最適化された値を選択するステップと、を含む。
【００３０】
本発明の第三態様において、請求項７に記載のシステムが提供される。
【００３１】
本発明の第四態様において、請求項１４に記載のコンピュータ・プログラム製品が提供される。
【００３２】
本発明の第五態様において、請求項１５に記載のコンピュータ・プログラムが提供される。
【００３３】
単なる例示として、添付の図面を参照しながら、以降に本発明の実施形態を説明する。
【図面の簡単な説明】
【００３４】
【図１】コンピュータ・システムにおける従来型のオプティマイザの展開図である。
【図２】好適な実施形態によるオプティマイザのコンポーネント図である。
【図３】該好適な実施形態の最適化方法の流れ図である。
【図４】図４Ａ、図４Ｂおよび図４Ｃは、線形計画法のコードの図である。
【図５】線形計画法のコードの図である。
【図６】図６Ａおよび６Ｂは、線形計画法のコードの図である。
【図７】本発明によって解かれた、生産計画の例に対する生産速度制約の表である。
【図８】この例に対する資源利用制約の表である。
【図９】この例に対する需要制約の表である。
【図１０】この例において示されるデータの特定の型に対するレジェンドを示す表である。
【図１１】この例のソリューション前の段階に対する、生産日数、未利用日数、および未利用日数の平方和を示す表の図である。
【図１２】この例のソリューション前の段階に対する、生産数を示す表である。
【図１３】この例のソリューション前の段階に対する、利用可能数、引き渡し数、未引き渡し数、在庫、および総計を示す表の図である。
【図１４】この例の線形ソリューション段階に対する、生産日数、未利用日数、および未利用日数の平方和を示す表の図である。
【図１５】この例の線形ソリューション段階に対する、生産数を示す表である。
【図１６】この例の線形ソリューション段階に対する、利用可能数、引き渡し数、未引き渡し数、在庫、および総計を示す表の図である。
【図１７】この例の二次ソリューション段階に対する、生産日数、未利用日数、および未利用日数の平方和を示す表の図である。
【図１８】この例の二次ソリューション段階に対する、生産数を示す表の図である。
【図１９】この例の二次ソリューション段階に対する、利用可能数、引き渡し数、未引き渡し数、在庫、および総計を示す表の図である。
【図２０】線形および二次計画段階からの生産日数表を比較した表の図である。
【発明を実施するための形態】
【００３５】
図１を参照すると、従来技術によるコンピュータ・システム・ノード１０のコンポーネント図が示されている。コンピュータ・システム・ノード１０は、数多くの他の汎用または特定用途のコンピューティング・システム、コンピューティング環境またはコンピューティング構成とともに動作可能なコンピュータ・システム／サーバ１２を含む。コンピュータ・システム／サーバ１２とともに用いるのに適し得る周知のコンピューティング・システム、コンピューティング環境またはコンピューティング構成は、以下に限らないが、パーソナル・コンピュータ・システム、サーバ・コンピュータ・システム、シン・クライアント、シック・クライアント、ハンドヘルドまたはラップトップ・デバイス、マルチプロセッサ・システム、マイクロプロセッサ・ベースのシステム、セット・トップ・ボックス、プログラマブル・コンシューマ・エレクトロニクス、ネットワークＰＣ、ミニコンピュータ・システム、メインフレーム・コンピュータ・システム、および上記のシステムまたはデバイスおよび類似デバイスの任意のものを含む分散型クラウド・コンピューティング環境が含まれる。
【００３６】
コンピュータ・システム／サーバ１２は、コンピュータ・システムによって実行されるプログラム・モジュールなど、コンピュータ・システム実行可能命令の一般的なコンテキストで説明することができる。一般に、プログラム・モジュールには、特定のタスクを遂行する、または特定の抽象データ型を実装する、ルーティン、プログラム、オブジェクト、コンポーネント、ロジック、データ構造体などを含めることが可能である。コンピュータ・システム／サーバ１２は、通信ネットワークを介してリンクされた遠隔の処理デバイスによってタスクが遂行される、分散型クラウド・コンピューティング環境の中に具現化することができる。分散型クラウド・コンピューティング環境では、プログラム・モジュールは、ローカルおよび遠隔コンピュータ・システムの両方の、メモリ・ストレージ・デバイスを含むストレージ媒体に配置することが可能である。
【００３７】
図１に見られるように、コンピュータ・システム・ノード１０中のコンピュータ・システム／サーバ１２は、汎用コンピューティング・デバイスの形で示されている。コンピュータ・システム／サーバ１２のコンポーネントには、以下に限らないが、一つ以上のプロセッサまたはプロセシング・ユニット１６、システム・メモリ２８、および、システム・メモリ２８のプロセッサ１６への連結を含めさまざまなコンポーネントを連結しているバス１８を含めることができる。
【００３８】
バス１８は、メモリ・バスまたはメモリ・コントローラ、周辺バス、アクセラレイティッド・グラフィックス・ポート、およびプロセッサ、またはさまざまなバス・アーキテクチャの任意のものを使ったローカル・バスを含め、バス構造体のいくつかの型の任意の一つ以上のものを表す。例示のためだけで限定ではないが、かかるアーキテクチャには、業界標準アーキテクチャ（ＩＳＡ）バス、マイクロ・チャネル・アーキテクチャ（ＭＣＡ）バス、拡張ＩＳＡ（ＥＩＳＡ）バス、ビデオ・エレクトロニクス・スタンダーズ・アソシエーション（ＶＥＳＡ）ローカル・バス、およびペリフェラル・コンポーネント・インターコネクト（ＰＣＩ）バスが含まれる。
【００３９】
コンピュータ・システム／サーバ１２は、通常、様々なコンピュータ・システム可読媒体を含む。かかる媒体は、コンピュータ・システム／サーバ１２がアクセス可能な任意の利用可能な媒体とすることができ、揮発性および不揮発性媒体の両方、リムーバブルおよびノンリムーバブル媒体の両方を含む。
【００４０】
システム・メモリ２８には、ランダム・アクセス・メモリ（ＲＡＭ）３０およびキャッシュ・メモリ３２など、揮発性メモリの形でコンピュータ・システム可読媒体を含めることができる。コンピュータ・システム／サーバ１２には、他のリムーバブル／ノンリムーバブル、揮発性／不揮発性のコンピュータ・システム・ストレージ媒体をさらに含めることが可能である。例示のためだけであるが、ノンリムーバブルで不揮発性の磁気媒体（図示しないが、通常「ハード・ドライブ」と呼ばれる）からの読み取りおよびこれへの書き込みのために、ストレージ・システム３４を設けることができる。図示していないが、リムーバブルな不揮発性磁気媒体（例えば、フレキシブル・ディスク）から読み取り、これに書き込むための磁気ディスク・ドライブ、およびＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭまたは他の光媒体などの、リムーバブルな不揮発性光ディスクに対し読み取り、書き込みを行うための光ディスク・ドライブを設けることが可能である。かかる例では、各々を、一つ以上のデータ媒体インターフェースによってバス１８に接続することができる。以下にさらに示し説明するように、メモリ２８には、本発明の実施形態の機能を遂行するよう構成された少なくとも一つのプログラム製品（例えば、オペレーティング・システム３６およびオプティマイザ４０）を含めることが可能である。
【００４１】
例示であって限定ではないが、オプティマイザ４０は、メモリ２８中にもオペレーティング・システム３６中にも格納することが可能である。プログラム・モジュールの各々はネットワーク環境の実装を含み得る。プログラム・モジュールは、一般に、本明細書に記載された本発明の実施形態の機能もしくは方法またはその両方を遂行する。
【００４２】
また、コンピュータ・システム／サーバ１２は、キーボード、ポインティング・デバイス、ディスプレイ２４など、一つ以上の外部デバイス１４；ユーザが、コンピュータ・システム／サーバ１２と相互作用できるようにする一つ以上のデバイス；もしくは、コンピュータ・システム／サーバ１２が一つ以上の他のコンピューティング・デバイスと通信できるようにする任意のデバイス（ネットワーク・カード、モデムなど）；またはこれらの組み合わせと通信することが可能である。かかる通信は、Ｉ／Ｏインターフェース２２を介して行うことができる。さらに、コンピュータ・システム／サーバ１２は、ネットワーク・アダプタ２０を介して、ローカル・エリア・ネットワーク（ＬＡＮ）、一般広域ネットワーク（ＷＡＮ）、もしくは公衆ネットワーク（例えばインターネット）またはこれらの組み合わせと通信することが可能である。図示のように、ネットワーク・アダプタ２０は、バス１８を介して、コンピュータ・システム／サーバ１２の他のコンポーネントと通信する。なお、図示されていないが、コンピュータ・システム／サーバ１２と併せ、他のハードウェアもしくはソフトウェアまたはその両方のコンポーネントを用いることができよう。その例には、以下に限らないが、マイクロコード、デバイス・ドライバ、冗長処理ユニット、外部ディスク・ドライブ・アレイ、ＲＡＩＤシステム、テープ・ドライブ、およびデータ記録ストレージ・システムが含まれる。
【００４３】
図２に示された好適な実施形態によるオプティマイザ４０は、最適化エンジン２０２、最適化データ２０４、および最適化方法２０６を含む。
【００４４】
最適化エンジン２０２は、ＩＢＭ（登録商標）  ＩＬＯＧ（登録商標）  ＣＰＬＥＸ  （登録商標）オプティマイザ・バージョン１２を使って供給された線形計画エンジンに基づいており、線形計画ソルバ２０８および二次計画ソルバ２０９を含む。ＩＢＭ（登録商標）  ＩＬＯＧ（登録商標）  ＣＰＬＥＸ（登録商標）は、線形計画、混合整数計画、二次計画、二次制約計画問題に対する、柔軟性のある、高性能の数理的計画ソルバを提供する。但し、任意の線形計画エンジンまたは混合整数計画エンジンを用いることが可能である。事例の表は、Ｍｉｃｒｏｓｏｆｔ  Ｅｘｃｅｌ（登録商標）２００３  Ｓｏｌｖｅｒアドイン線形計画ソルバ・コンポーネントを使って作成された。ＭｉｃｒｏｓｏｆｔおよびＥｘｃｅｌは、米国その他の国におけるマイクロソフト・コーポレイションの商標である。
【００４５】
線形計画ソルバ２０８は周知であり、特定の制約Ｘを用い、ＣＸを最適化するためＡＸ＋Ｙ＝Ｂ型の線形問題を解くためのものである。
【００４６】
二次計画ソルバ２０９も周知であり、特定の制約Ｘを用い、最適化のため（ＤＸ）＾２＋ＣＸ＝Ｂ型の二次問題を解くためのものである。
【００４７】
最適化データ２０４は、線形関数２１０、制約２１２、第一最適解２１４、スラック変数２１６、二次関数２１８、および均衡解２２０を含む。
【００４８】
線形関数２１０は、ＡＸ＋Ｙ＝Ｂ型のメモリ中に格納された数理計画関数であって、この式のＡおよびＢは定数であり、ＸおよびＹは解決が必要な変数である。コードの例では、線形関数は、文字「ｍｐｓ」で表されている。
【００４９】
制約２１２は、値ＸおよびＹが取り得る値の制限である。コードの例では、制約は、マトリックスＭで表されている。
【００５０】
最適解２１４は、線形計画ソルバ２０８によって最適として計算された解である。この好適な実施形態では、ただ一つの最適解が格納される。
【００５１】
スラック変数２１６は、不等制約を等価に変換するためにそれに加算される変数を格納する。スラック変数を導入することによって、不等制約を、等価制約且つ非負制約に置き換える。
【００５２】
二次関数２１８は、メモリ中に格納された、（ＤＸ）＾２＋ＡＸ＋Ｙ＝Ｂ型の数理計画関数であって、この式のＡ、ＢおよびＤは定数であり、ＸおよびＹは解決対象の変数である。
【００５３】
均衡解２２０は、二次計画ソルバ２０９によって解かれた解である。
【００５４】
好適な実施形態の最適化方法２０６は、図３に示されるように、論理プロセス・ステップ３０２〜３１６を含む。
【００５５】
ステップ３０２は、所与の制約２１２の線形関数２１０を解くためのステップである。
【００５６】
ステップ３０４は、第一最適解２１４を利用可能にするためのステップである。
【００５７】
ステップ３０６は、最適解２１４を新規関数２１８に対する制約として加算するためのステップである。
【００５８】
ステップ３０８は、新規関数２１８に対する制約としてスラック変数制約を加算するためのステップである。
【００５９】
ステップ３１０は、二次目的を線形関数２１０に加え、二次関数２１８を生成するためのステップである。
【００６０】
ステップ３１２は、与えられた旧制約および新規制約による二次関数を解くためのステップである。
【００６１】
ステップ３１４は、線形問題に対する妥協解である、二次問題に対する解Ｘ１を提供するためのステップである。
【００６２】
ステップ３１６は、この方法の終了である。
【００６３】
図４Ａ〜６Ｂは、本方法の線形計画段階のコードの図であり、該コードはライン１〜５０を有する。以下で、本最適化方法の特定のステップで識別されたコードを呼び出すことがあり、「／／／」区切り記号の後に追加のコメントを記載する。呼び出されない他のコードも本実施形態に関連するものである。「／／」は、コードの図中のコメントを表しているが、これらは必ずしも以下の説明中の対応コメントと同じではない。
【００６４】
図４Ａのコードは、該最適化方法のステップ３０２を表す。
【００６５】
ライン１「ｒｅａｄ  ｍｐｓ  ｍａｔｒｉｘ  Ｍ」／／このｒｅａｄは、線形ソルバに、線形問題ｍｐｓおよび制約Ｍを取得させる命令である。
【００６６】
ライン３「ｓｏｌｖｅ  ｔｈｅ  ＭＩＰ  ｐｒｏｂｌｅｍ  ｕｓｉｎｇ  ＭＩＰ」／／／これは、ＭＩＰ（ＩＢＭ（登録商標）  ＩＬＯＧ（登録商標）  ＣＰＬＥＸ（登録商標）問題解決エンジンの一つ）と呼ばれる線形ソルバに、問題を解かさせる命令である。
【００６７】
図４Ｂ中のコードは、該最適化方法のステップ３０４を表す。
【００６８】
ライン４「ｄｏｕｂｌｅ  ０１＝ｏｐｔｉｍａｌ  ｖａｌｕｅ」／／／これは、該ソルバの最適値の出力となる変数を設定する。
【００６９】
図４Ｃ中のコードは、上記の最適化方法のステップ３０６を表す。
【００７０】
ライン５「ｇｅｔ  ｏｂｊｅｃｔｉｖｅ  Ｏｂｊ  ｆｒｏｍ  Ｍ；」、
ライン６「ｇｅｔ  ｅｐｓｉｌｏｎ  ｆｒｏｍ  ｐａｒａｍｅｔｅｒｓ；」、
ライン７「ａｄｄ  ｃｏｎｓｔｒａｉｎｔｓ  ０１−ｅｐｓｉｌｏｎ＜＝Ｏｂｊ＜＝０１＋ｅｐｓｉｌｏｎ；」／／／これは、新規制約に解０１（最適値）を含めることを命令する。
【００７１】
図５のコードは、該最適化方法のステップ３０８にスラック変数を加えることによる新規制約の形成を表す。不等、下界変数、および上界変数は別個に取り扱われる。
【００７２】
図６Ａ中のコードのライン３９〜４４は、最適化方法のステップ３１０において二次方程式を解くステップを表す。
【００７３】
ライン４４「ｍｉｎｉｍｉｚｅ  ｑ，  ｕｎｄｅｒ  ｃｏｎｓｔｒａｉｎｔｓ  ｉｎ  Ｍ；」／／／これは、二次問題ソルバ（ＱＰ−ソルバ）に、マトリックスＭ中の新規制約の制約下で、ｑを最小化することによって問題を解くよう命令する。
【００７４】
図６Ｂ中のコードのライン４５〜５０は、最適化方法のステップ３１２での解「ｖ」の出力を表す。
【００７５】
図７は、本発明によって解かれた、生産計画の例に対する生産速度制約の表である。この生産計画の例において、生産速度（ＰＲ）はある所与の工場によって一日に生産される自動車の数である。３つの工場、工場１、工場２、および工場３があり、対応する３つの生産速度、ＰＲ１、ＰＲ２、およびＰＲ３がある。この例において、工場２は、その生産速度において、ある差異で他の工場に立ち遅れている。
【００７６】
図８は、この例に対する資源利用性制約の表である。
【００７７】
資源利用性（ＲＡ）は、ある特定の週において各工場が利用できる日数である。３つの週、週１、週２、および週３がある。資源利用性が表の中に表されているが、マトリックスであらわすることもできよう。
【００７８】
図９は、この例に対する需要（ＤＤ）制約の表である。需要は、ある所与の週において必要な自動車の数である。３つの異なる需要、ＤＤ１＝１０、ＤＤ２＝１０、およびＤＤ３＝１５０があり、週３は、１桁多い最大の需要を有する。
【００７９】
図１０は、この例の中で示されるデータの特定の型に対するレジェンドを示す表である。全データが通常の実線内に表されているが、一部のデータは強調に値する。目的は、最適化される関数の部分であり、太い実線で強調されている。一つの目的は、在庫および未引き渡しの品目の合計を最小化することとして定義されている。別の目的は、未利用日数の平方和を最小化することである。
【００８０】
非負制約は、正かゼロの制約であり、対象値の周りの太い点線で強調されている。図１１、１３および１７において、未利用日数が、非負制約として強調されている。図１３、１６、および１９では、未引き渡しの自動車の数が、非負制約としてマークされ、週末時の在庫（Ｉ）も非負制約として強調されている。
【００８１】
決定変数は、対象値の周りの太い破線によって強調されている。図１１、１４、および１７において、生産日数が、決定変数としてマークされ強調されている。図１３、１６、および１９では、ある週に引き渡された自動車の数が強調されており、決定変数としてマークされている。
【００８２】
図１１は、この例のソリューション前の段階に対する、生産日数、未利用日数、および未利用日数の平方和を示す表の図である。
【００８３】
生産日数（ＰＤ）は、ある所与の週である工場が生産可能な日数である。これは、決定変数であり、したがって、ソリューションが開始される前は、これは空変数であるか、またはある所与の週および工場に与えられた生産日を表す変数だけによって標識されたマトリックス：ＰＤ１１、ＰＤ２１、ＰＤ３１、ＰＤ１２、ＰＤ２２、ＰＤ３２、ＰＤ１３、ＰＤ２３、ＰＤ３３である。ある所与の週に対する合計生産日数は、ΣＰＤ１ｘ、ΣＰＤ２ｘ、およびΣＰＤ３ｘで表される。
【００８４】
未利用日数（ＵＤ）は、ある所与の工場がある所与の週に利用されなかった日数であり、それぞれの資源利用性（ＲＡ）からを生産日数（ＰＤ）減じることによって計算される。ＵＤが決して負にならないようにこれを定義することによって、ＵＤは非負制約になる。ソリューションを開始する前は、生産日数に対する値はない、したがって、生産日数を用いた未利用日数に対する値もない。
【００８５】
未利用日数の平方和は、二次変数であり二次問題の目的である。方程式を解く前は生産日数は未知なので、未利用日数の平方和も未知である。
【００８６】
図１２は、この例のソリューション前の段階に対する、生産数を示す表である。
【００８７】
生産数（ＱＰ）は、生産日数（ＰＤ）と生産速度（ＰＲ）との積として得られた、ある工場によってある所与の週に生産される自動車の数である。これは、決定変数に依存し、したがって解かれるまで未知である。
【００８８】
図１３は、この例のソリューション前の段階に対する、利用可能数、引き渡し数（Ｄ）、未引き渡し数（ＮＤ）、在庫（Ｉ）、および総計を示す表の図である。
【００８９】
利用可能数（Ａ）は、ある所与の週に引き渡しに利用可能な自動車の数であり、所与の週における合計生産数（ＴＱＰ）＋在庫（Ｉ）によって定義される。
【００９０】
引き渡し数（Ｄ）はある所与の週に引き渡される自動車の数である。これは決定変数である。
【００９１】
未引き渡し数（ＮＤ）は、ある所与の週に引き渡されない自動車の数であり、需要（ＤＭ）マイナス引き渡し（Ｄ）として定義される。ＮＤは非負制約である。
【００９２】
在庫数（Ｉ）は、週末時の在庫であり、週始めの在庫（Ｉ）＋利用可能（ＡＶ）−引き渡し（Ｄ）として定義される。Ｉは非負制約である。
【００９３】
週末時の総計は、未引き渡し（ＮＤ）プラスその週末時の在庫である。未引き渡しと在庫との合計数の最小化は、未利用日数の平方和の最小化とともに、目的として設定される。
【００９４】
図１４は、この例の線形ソリューション段階に対する、生産日数、未利用日数、および未利用日数の平方和を示す表の図である。図のソリューションは、線形ソリューションであり、これでは合計未引き渡しだけがゼロに最小化さている（図１６を参照）。最後の週で、最も効率の良い工場の生産日数が非常に多忙であるのが見られ、これは最適解として考慮されるが、あまり均衡のとれたものではない。生産日数が週３においてきつかったこととして、未利用日数表中に、週１および週２と工場２で極めて多くの未利用日数があるのが見られる。さらに、この線形ソリューションでは使われていないが、より多くの未利用日数があれば、未利用日数の平方和がより高くなるであろうことが分かる。図の９１．２５は、例えば図１７において可能な数に比べると高い数である。
【００９５】
ある工場で最後の週に問題が生じたとすればどうなるであろうか？理想的には、もっと均衡の取れたソリューションを選択できよう。それが図１７、１８、および１９に示された新規の目的である。
【００９６】
図１５は、この例の線形ソリューション段階に対する、生産数を示す表である。これらの数は、週３での工場１および３の生産におけるすさまじい努力を反映している。
【００９７】
図１６は、この例の線形ソリューション段階に対する、利用可能数、引き渡し数、未引き渡し数、在庫、および総計を示す表の図である。未引き渡しおよび在庫の合計を最小に保つという当初の目的は、週３においてほとんどの引き渡し（１５０台の自動車）を行うことによって、達成されたことが示されている。
【００９８】
図１７は、この例の二次ソリューション段階に対する、生産日数、未利用日数、および未利用日数の平方和を示す表の図である。この例において、解決対象の新規二次目的を設定するために未利用日数が使われており、ここでは、二次ソルバが未利用日数の平方和、および合計未引き渡しを最小化しようとしている。生産日数が、週および工場を通してより均等に配分されているのが見られ、工場２も稼働されている。
【００９９】
図１８は、この例の二次ソリューション段階に対する、生産数を示す表の図である。この図では、週に亘ってさらに均等に分配されているのが見られる。
【０１００】
図１９は、この例の二次ソリューション段階に対する、利用可能数、引き渡し数、未引き渡し数、在庫、および総計を示す表の図である。このソリューションは、前と同様、合計未引き渡しプラス在庫を最小に保つために制約されているが、今回は引き渡しのため利用可能な自動車を増大させているのが見られる。
【０１０１】
図２０は、線形および二次計画段階からの生産日数表を比較した表の図であり、より均等な分配が見られる。
【０１０２】
以降に本発明のさらなる実施形態を説明する。
【０１０３】
当業者には、好適な実施形態の方法の全部または一部を、本方法のステップを実行するよう配置された論理エレメントを含むさらなる単複数の論理装置中に適切かつ有用に具現できること、およびかかる論理エレメントには、さらなるハードウェア・コンポーネント、ファームウェア・コンポーネント、またはこれらの組み合わせを含めることが可能なことは明瞭であろう。
【０１０４】
当業者には、好適な実施形態の機能コンポーネントの一部または全部を、同等な方法ステップを用いる同等な機能を実行するための論理エレメントを含む、別の単複数の論理装置中に適切に具現できること、およびかかる論理エレメントには、例えば、プログラム可能論理アレイまたは特定用途向け集積回路中の論理ゲートなどのコンポーネントを含めることが可能なことも同様に明瞭であろう。かかる論理エレメントは、例えば、仮想ハードウェア・ディスクリプタ言語（これは固定または伝送可能キャリヤ媒体を用い格納および送信が可能である）を使って、かかるアレイまたは回路中に論理構造を一時的にまたは恒久的に構築するために、実現エレメント中にさらに具現することができる。
【０１０５】
当然ながら、前述の方法およびアレンジメントは、一つ以上のプロセッサ（図示せず）上で実行されるソフトウェアで、全面的にまたは部分的に適切に遂行することも可能であり、かかるソフトウェアは、磁気または光ディスクなど任意のデータキャリヤ（これも図示せず）で搬送される、一つ以上のコンピュータ・プログラム・エレメントの形で提供することができる。同様に、データの伝送のためのチャネルは、前述のすべてのストレージ媒体、および有線または無線の信号搬送媒体などの信号搬送媒体を含み得る。
【０１０６】
さらに、本発明は、コンピュータ・システムと併せて使用するためのコンピュータ・プログラム製品として適切に具現化することができる。かかる実装には、例えばディスケット、ＣＤ−ＲＯＭ、ＲＯＭ、またはハード・ディスクなどのコンピュータ可読媒体などの有形媒体上に固定された；もしくは、以下に限らないが光または類似の通信ラインを含む有形の媒体を介して、あるいは以下に限らないがマイクロ波、赤外線、または他の送信技法を含む無線技法を使い無形で、モデムまたは他のインターフェース・デバイスを用いてコンピュータ・システムに送信可能な；一連のコンピュータ可読命令を含めることが可能である。この一連のコンピュータ可読命令は、本明細書中で前述した機能の全部または一部を具現化する。
【０１０７】
当業者は、かかるコンピュータ可読命令が、多くのコンピュータ・アーキテクチャまたはオペレーティング・システムとともに使用するため、多くのプログラミング言語で記述できることをよく理解していよう。さらに、かかる命令は、以下に限らないが、半導体、磁気、または光を含め、現在または将来の任意のメモリ技術を用いて格納する、あるいは、以下に限らないが、光、赤外線またはマイクロ波を含め、現在または将来の任意の通信技術を用いて送信することができる。かかるコンピュータ・プログラム製品は、例えば、コンピュータにプリロードするため、システムＲＯＭまたは固定ディスク上などにパッケージ化ソフトウェアなどのリムーバブル媒体を、印刷または電子文書を添えて配布する、もしくは、サーバ、あるいは、例えばインターネットまたはワールド・ワイド・ウェブなどのネットワークを介した電子掲示板から配布することも考えられる。
【０１０８】
別案において、本発明の好適な実施形態は、コンピュータ・インフラストラクチャに展開されその上で実行されたとき、該コンピュータ・システムに本方法の全ステップを遂行させるよう作動するコンピュータ・プログラム・コードを展開するステップを含む、サービスを展開するコンピュータ実装の方法の形で実現することができる。
【０１０９】
さらなる別案において、本発明の好適な実施形態を機能データを有するデータ・キャリヤの形で実現し、前記機能データがコンピュータ・システムにロードされそれにより作動されたとき、前記コンピュータ・システムが本方法の全ステップを遂行できるようにするための、機能的コンピュータ・データ構造体を含むようにすることが可能である。
【０１１０】
当業者には、本発明の範囲から逸脱することなく、前述の例示的実施形態に多くの改良および修改を加えることが可能なことは明瞭であろう。
【図１】
2015501057.tif 000003
【図２】
2015501057.tif 000004
【図３】
2015501057.tif 000005
【図４】
2015501057.tif 000006
【図５】
2015501057.tif 000007
【図６】
2015501057.tif 000008
【図７】
2015501057.tif 000009
【図８】
2015501057.tif 000010
【図９】
2015501057.tif 000011
【図１０】
2015501057.tif 000012
【図１１】
2015501057.tif 000013
【図１２】
2015501057.tif 000014
【図１３】
2015501057.tif 000015
【図１４】
2015501057.tif 000016
【図１５】
2015501057.tif 000017
【図１６】
2015501057.tif 000018
【図１７】
2015501057.tif 000019
【図１８】
2015501057.tif 000020
【図１９】
2015501057.tif 000021
【図２０】
2015501057.tif 000022
【手続補正書】
【提出日】平成26年7月8日(2014.7.8)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
コンピュータ化された多重制約問題空間における最適化解を選択するための方法であって、前記方法は、
最適化のための線形関数を受信するステップと、
前記線形関数に対する制約のセットを受信するステップと、
線形計画ソルバを用いて前記線形関数および初期制約に対する第一最適解を算定するステップと、
前記初期制約と併せ前記第一最適解を制約として用いて、制約の新規セットを生成するステップと、
前記線形関数にスラック変数の二次目的を加えることによって、新規二次関数を生成するステップと、
二次計画ソルバを用いて前記二次関数および新規制約に対する解を算定するステップと、
を含む、方法。
【請求項２】
スラック変数制約が重み付けのデフォルト・セットを有する、請求項１に記載の方法。
【請求項３】
前記スラック変数制約は、管理者またはユーザが決定した一つ以上の費用係数に基づいている、請求項２に記載の方法。
【請求項４】
前記線形関数は整数関数とすることが可能な、請求項１〜３のいずれかに記載の方法。
【請求項５】
請求項１に記載の方法を使ってデバイスを制御する方法。
【請求項６】
コンピュータ化された多重制約問題空間において一つ以上の最適化された値を選択するための方法であって、前記方法は、
混合整数計画コンポーネントの入力値の第一セット、線形計画コンポーネントの入力値の第二セット、およびユーザが決定した一つ以上の費用係数に基づく、平方スラック変数制約の費用重み付けされたセットを入力として受信するステップと、
前記混合整数計画コンポーネントの出力値の第一セットを生成するステップと、
前記線形計画コンポーネントの出力値の第二セットを生成するステップと、
前記出力値の第一セットおよび前記出力値の第二セットに従って制限解空間を生成するステップと、
前記ユーザが決定した一つ以上の費用係数に基づく前記平方スラック変数制約の費用重み付けされたセットに基づいて、さらなる制限を適用することによって、前記制限解空間から最適化された値を選択するステップと、
を含む、方法。
【請求項７】
コンピュータ化された多重制約問題空間における最適化解を選択するためのシステムであって、前記システムは、
最適化のための線形関数を受信するための手段と、
前記線形関数に対する制約のセットを受信するための手段と、
前記線形関数および初期制約に対する第一最適解を算定するための線形計画ソルバと、
前記初期制約と併せ前記第一最適解を制約として用いて、制約の新規セットを生成するための手段と、
前記線形関数にスラック変数の二次目的を加えることによって、新規二次関数を生成するための手段と、
二次計画ソルバを用いて前記二次関数および新規制約に対する解を算定するための二次ソルバと、
を含む、システム。
【請求項８】
スラック変数制約が重み付けのデフォルト・セットを有する、請求項７に記載のシステム。
【請求項９】
前記スラック変数制約は、管理者またはユーザが決定した一つ以上の費用係数に基づいている、請求項８に記載のシステム。
【請求項１０】
前記線形関数は整数関数とすることが可能な、請求項７〜９のいずれかに記載のシステム。
【請求項１１】
請求項１〜５のいずれかに記載の方法を用いるデバイスを制御するためのコントローラ。
【請求項１２】
コンピュータ化された多重制約問題空間における最適化解を選択するためのコンピュータ可読コードが格納されたコンピュータ可読記録媒体であって、前記コンピュータ可読コードは、コンピュータ・システムにロードされ実行されたとき、
最適化のための線形関数を受信するステップと、
前記線形関数に対する制約のセットを受信するステップと、
線形計画ソルバを用いて前記線形関数および初期制約に対する第一最適解を算定するステップと、
前記初期制約と併せ前記第一最適解を制約として用いて、制約の新規セットを生成するステップと、
前記線形関数にスラック変数の二次目的を加えることによって、新規二次関数を生成するステップと、
二次計画ソルバを使って、前記二次関数および新規制約に対する解を算定するステップと、
を前記コンピュータ・システムに実行させる、コンピュータ可読記録媒体。
【請求項１３】
スラック変数制約が重み付けのデフォルト・セットを有する、請求項１２に記載のコンピュータ可読記録媒体。
【請求項１４】
前記スラック変数制約は、管理者またはユーザが決定した一つ以上の費用係数に基づいている、請求項１３に記載のコンピュータ可読記録媒体。
【請求項１５】
コンピュータ可読媒体に格納され、デジタル・コンピュータの内部メモリにロード可能なコンピュータ・プログラムであって、請求項１〜５のいずれかに記載の方法の各ステップをコンピュータに実行させるためのコンピュータ・プログラム。
【国際調査報告】
2015501057.tif 000023
2015501057.tif 000024