(57)【要約】【課題】違反制約極小集合の算出にかかる時間を削減できる違反制約算出システムを提供する。【解決手段】違反制約算出システム１０は、変更対象のシステムの構成要素の状態を仮想的に変更することによって変更対象のシステムの構成を変更目的の構成まで仮想的に変更する変更手段１１と、仮想的に変更される構成要素の状態に課される制約のうち充足されていない制約である違反制約を変更対象のシステムの構成が仮想的に変更されている間に算出する算出手段１２とを含む。【選択図】図５
2018120457.tif 000002
【特許請求の範囲】
【請求項１】
変更対象のシステムの構成要素の状態を仮想的に変更することによって前記変更対象のシステムの構成を変更目的の構成まで仮想的に変更する変更手段と、
仮想的に変更される前記構成要素の状態に課される制約のうち充足されていない制約である違反制約を前記変更対象のシステムの構成が仮想的に変更されている間に算出する算出手段とを含む
ことを特徴とする違反制約算出システム。
【請求項２】
算出された違反制約の集合のうち他の集合を包含しない集合である極小な集合を記憶する記憶手段を含む
請求項１記載の違反制約算出システム。
【請求項３】
算出手段は、
変更対象のシステムの構成が変更目的の構成まで仮想的に変更された時点で算出された違反制約の集合と記憶手段に記憶されている違反制約の極小な集合とを比較し、
記憶されている違反制約の極小な集合に含まれている要素と同じ数の要素が含まれている算出された違反制約の集合を前記記憶手段に追加する
請求項２記載の違反制約算出システム。
【請求項４】
変更手段は、変更対象のシステムの構成が変更目的の構成に仮想的に変更されるまでの前記変更対象のシステムの構成要素の状態を仮想的に変更する複数の手順ごとに前記変更対象のシステムの構成を変更する
請求項１から請求項３のうちのいずれか１項に記載の違反制約算出システム。
【請求項５】
変更対象のシステムの構成要素の状態を仮想的に変更することによって前記変更対象のシステムの構成を変更目的の構成まで仮想的に変更し、
仮想的に変更される前記構成要素の状態に課される制約のうち充足されていない制約である違反制約を前記変更対象のシステムの構成が仮想的に変更されている間に算出する
ことを特徴とする違反制約算出方法。
【請求項６】
算出された違反制約の集合のうち他の集合を包含しない集合である極小な集合を記憶する
請求項５記載の違反制約算出方法。
【請求項７】
変更対象のシステムの構成が変更目的の構成まで仮想的に変更された時点で算出された違反制約の集合と記憶されている違反制約の極小な集合とを比較し、
記憶されている違反制約の極小な集合に含まれている要素と同じ数の要素が含まれている算出された違反制約の集合を記憶する
請求項６記載の違反制約算出方法。
【請求項８】
コンピュータに、
変更対象のシステムの構成要素の状態を仮想的に変更することによって前記変更対象のシステムの構成を変更目的の構成まで仮想的に変更する変更処理、および
仮想的に変更される前記構成要素の状態に課される制約のうち充足されていない制約である違反制約を前記変更対象のシステムの構成が仮想的に変更されている間に算出する算出処理
を実行させるための違反制約算出プログラム。
【請求項９】
コンピュータに、
算出された違反制約の集合のうち他の集合を包含しない集合である極小な集合を記憶する記憶処理を実行させる
請求項８記載の違反制約算出プログラム。
【請求項１０】
コンピュータに、
変更対象のシステムの構成が変更目的の構成まで仮想的に変更された時点で算出された違反制約の集合と記憶されている違反制約の極小な集合とを比較する比較処理、および
記憶されている違反制約の極小な集合に含まれている要素と同じ数の要素が含まれている算出された違反制約の集合を記憶する記憶処理を実行させる
請求項９記載の違反制約算出プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、違反制約算出システム、違反制約算出方法および違反制約算出プログラムに関し、特に緩和対象である制約の部分集合を全て算出できる違反制約算出システム、違反制約算出方法および違反制約算出プログラムに関する。
【背景技術】
【０００２】
システムの変更計画において、変更開始前の任意のシステム構成、変更中の任意のシステム構成、または変更終了後の任意のシステム構成のいずれにおいても充足が求められる制約を状態制約と呼ぶ。また、変更計画で使用される構成の変更手順に従って変更されている任意のシステム構成で充足されていない状態制約を違反制約と呼ぶ。
【０００３】
また、緩和されれば変更手順が存在するような違反制約の集合を違反制約集合と呼ぶ。また、違反制約集合のうち極小な集合を違反制約極小集合と呼ぶ。なお、「極小な集合（以下、極小集合ともいう。）」は、集合間に包含関係が定義されている場合に他の集合を包含しない集合である。
【０００４】
違反制約算出システムは、上記のような違反制約を算出するシステムである。一般的な違反制約算出システムの一例が、特許文献１〜特許文献３に記載されている。特許文献１には、LSI(Large Scale Integration)の配線パターンを求める配線パターン決定方法が記載されている。
【０００５】
LSIの配線作業では、例えば配線が禁止されている領域（以下、禁止領域という。）が状態制約として与えられる。状態制約（禁止領域）が多く設けられると、配線計画が生成されない場合がある。
【０００６】
しかし、配線計画が生成されない場合に設けられている状態制約のうちいくつかの状態制約が除かれることによって、配線計画が生成される可能性がある。すなわち、特許文献１に記載されている配線パターン決定方法では、配線計画が生成されるために除かれた状態制約（禁止領域）の集合が、緩和されることによって配線計画の生成が可能になる「違反制約集合」とみなされる。
【０００７】
また、特許文献２には、看護師の勤務計画を立案するスケジューリング装置が記載されている。特許文献２に記載されているスケジューリング装置が勤務計画を立案する際、例えば何人かの看護師は夜勤が禁止されている等の状態制約が与えられている。与えられている全ての状態制約を満たしつつ勤務計画を生成する時、スケジューリング装置は、勤務計画を生成できない場合がある。
【０００８】
勤務計画を生成できない場合、特許文献２に記載されているスケジューリング装置は、例えば与えられている複数の状態制約それぞれに優先度を設け、優先度の低い状態制約を除いた上で再度勤務計画の立案を試みる。残った状態制約の集合を満たす勤務計画が立案されれば、立案の前に削除された状態制約の集合が、緩和されることによって勤務計画の立案が可能になる「違反制約集合」とみなされる。
【０００９】
また、特許文献３には、複数のコンテンツの選択に係る制約条件や、複数のコンテンツの時間的な配列に係る制約条件に基づいて、制約解消技術を利用して番組表を作成する番組表作成方法が記載されている。
【００１０】
特許文献１に記載されている配線パターン決定方法および特許文献２に記載されているスケジューリング装置のように、与えられている状態制約を少しずつ緩和し、求解できた時点で緩和された状態制約の集合を違反制約集合とする方式を一般化することを考える。
【００１１】
すなわち、上記の方式を変更手順を求める変更計画問題に適用することによって、計画問題の解が求められない場合に違反制約極小集合を全て求める方法を考える。なお、違反制約集合のうち極小集合を求める理由は、手順生成の際に除去される違反制約はできるだけ少ない方が得られる解が真の解に近くなるためである。
【００１２】
図６は、一般的な違反制約算出システムの構成例を示すブロック図である。図６に示す違反制約算出システム１０は、変更計画問題の解が求められない場合に違反制約極小集合を全て求めるシステムである。
【００１３】
図６に示すように、違反制約算出システム１０は、違反制約算出装置９００と、出力手段２００とを含む。また、違反制約算出装置９００は、制約制御手段９１０と、制約格納手段９２０と、手順生成手段９３０と、手順存在確認手段９４０と、極小違反集合追加手段９５０と、制約全体集合格納手段９６０と、極小集合格納手段９７０と、違反制約集合格納手段（図示せず）とを含む。
【００１４】
以下、図６に示す違反制約算出システム１０の違反制約極小集合を算出する動作を図７を参照して説明する。図７は、一般的な違反制約算出システムによる違反制約極小集合算出処理の動作を示すフローチャートである。
【００１５】
制約制御手段９１０は、最初に制約格納手段９２０に全ての状態制約を格納する（ステップS901）。次いで、手順生成手段９３０は、制約格納手段９２０に状態制約が格納されているか否かを確認する（ステップS902）。
【００１６】
制約格納手段９２０に状態制約が格納されていない場合、すなわち制約格納手段９２０が空である場合（ステップS902におけるYes）、違反制約算出システム１０は、違反制約極小集合算出処理を終了する。
【００１７】
制約格納手段９２０に状態制約が格納されている場合（ステップS902におけるNo）、手順生成手段９３０は、制約格納手段９２０に格納されている全ての状態制約が充足されるような変更手順を生成する（ステップS903）。
【００１８】
次いで、手順存在確認手段９４０は、手順生成手段９３０が変更手順を生成できたか否かを確認する（ステップS904）。変更手順が生成された場合（ステップS904におけるYes）、極小違反集合追加手段９５０は、制約全体集合格納手段９６０に格納されている制約全体集合と制約格納手段９２０に格納されている状態制約との差集合を求める。制約全体集合格納手段９６０には、充足対象の全ての状態制約、すなわち状態制約の全体集合が格納されている。
【００１９】
極小違反集合追加手段９５０は、求められた差集合を、緩和されると変更手順が生成される違反制約の集合と判断する。次いで、極小違反集合追加手段９５０は、既に極小集合格納手段９７０に格納されている違反制約の集合と求められた差集合とを比較する。
【００２０】
比較した結果、算出された違反制約の集合が極小な集合であれば、極小違反集合追加手段９５０は、算出された違反制約の集合を極小集合格納手段９７０に追加する（ステップS905）。
【００２１】
変更手順が生成されない場合（ステップS904におけるNo）、制約制御手段９１０は、制約格納手段９２０に格納されている状態制約のうち削除対象の状態制約を決定する（ステップS906）。決定した後、制約制御手段９１０は、制約格納手段９２０から削除対象の状態制約を削除する（ステップS907）。削除した後、違反制約算出システム１０は、再度ステップS902の処理を行う。
【００２２】
図７に示す違反制約極小集合算出処理において、制約制御手段９１０は、制約全体集合を基に生成される部分集合を全て選択する。制約制御手段９１０は、選択された部分集合を制約格納手段９２０に格納する。選択された各部分集合に関して、手順生成手段９３０は、変更手順を生成可能か否かをそれぞれ確認する。
【００２３】
よって、図６に示す違反制約算出システム１０は、図７に示す違反制約極小集合算出処理を実行することによって、緩和されると変更手順が生成される違反制約の極小集合を全て算出できる。
【先行技術文献】
【特許文献】
【００２４】
【特許文献１】特開平０４−１６０５７１号公報
【特許文献２】特開２０１５−２２２４６４号公報
【特許文献３】国際公開第２００５／０９６６２９号
【特許文献４】特開平０７−２３９８３９号公報
【発明の概要】
【発明が解決しようとする課題】
【００２５】
図６に示す違反制約算出システム１０における第１の問題点は、緩和対象である違反制約の集合である違反制約集合のうちの極小集合を全て求めるまでに多くの計算時間がかかるという点である。
【００２６】
その理由は、図７に示す違反制約極小集合算出処理では、制約全体集合を基に生成される各部分集合に対して手順生成手段９３０が変更手順を逐一生成するためである。手順生成手段９３０による手順生成処理には、一般的に多くの計算時間を要する。すなわち、全ての違反制約の極小集合が求められるまでに何度も手順生成処理が実行されると、処理全体の計算時間が長くなる。
【００２７】
例えば、特許文献４には、局所最適解から容易に脱出して短時間で制約充足解を得る制約充足問題処理方式が記載されている。特許文献４に記載されている制約充足問題処理方式も、全てのパターンを探索した後に違反制約の数が最小の集合を選択するため、多くの探索時間を要する。
【００２８】
従って、緩和対象の状態制約の集合である違反制約集合のうちの極小集合を全て求める際に多くの計算時間がかかるという課題を解決できる違反制約算出システムが求められている。
【００２９】
［発明の目的］
そこで、本発明は、上述した課題を解決する、違反制約極小集合の算出にかかる時間を削減できる違反制約算出システム、違反制約算出方法および違反制約算出用プログラムを提供することを目的とする。
【課題を解決するための手段】
【００３０】
本発明による違反制約算出システムは、変更対象のシステムの構成要素の状態を仮想的に変更することによって変更対象のシステムの構成を変更目的の構成まで仮想的に変更する変更手段と、仮想的に変更される構成要素の状態に課される制約のうち充足されていない制約である違反制約を変更対象のシステムの構成が仮想的に変更されている間に算出する算出手段とを含むことを特徴とする。
【００３１】
本発明による違反制約算出方法は、変更対象のシステムの構成要素の状態を仮想的に変更することによって変更対象のシステムの構成を変更目的の構成まで仮想的に変更し、仮想的に変更される構成要素の状態に課される制約のうち充足されていない制約である違反制約を変更対象のシステムの構成が仮想的に変更されている間に算出することを特徴とする。
【００３２】
本発明による違反制約算出プログラムは、コンピュータに、変更対象のシステムの構成要素の状態を仮想的に変更することによって変更対象のシステムの構成を変更目的の構成まで仮想的に変更する変更処理、および仮想的に変更される構成要素の状態に課される制約のうち充足されていない制約である違反制約を変更対象のシステムの構成が仮想的に変更されている間に算出する算出処理を実行させることを特徴とする。
【発明の効果】
【００３３】
本発明によれば、違反制約極小集合の算出にかかる時間を削減できる。
【図面の簡単な説明】
【００３４】
【図１】本発明による違反制約算出システム１０の第１の実施形態の構成例を示すブロック図である。
【図２】第１の実施形態の違反制約算出装置１００による違反制約極小集合算出処理の動作を示すフローチャートである。
【図３】通信ネットワーク構成の例を示す説明図である。
【図４】第１の実施形態の違反制約算出装置１００による探索の履歴の例を示す説明図である。
【図５】本発明による違反制約算出システムの概要を示すブロック図である。
【図６】一般的な違反制約算出システムの構成例を示すブロック図である。
【図７】一般的な違反制約算出システムによる違反制約極小集合算出処理の動作を示すフローチャートである。
【発明を実施するための形態】
【００３５】
［第１の実施形態］
［構成の説明］
以下、本発明の実施形態を、図面を参照して説明する。図１は、本発明による違反制約算出システム１０の第１の実施形態の構成例を示すブロック図である。図１に示すように、本実施形態の違反制約算出システム１０は、違反制約算出装置１００と、出力手段２００とを含む。
【００３６】
本実施形態の違反制約算出装置１００は、計画されたシステム構成の変更の任意の段階で充足が求められる状態制約の集合が与えられている変更計画問題を解くことによって、状態制約が充足される変更手順を算出する。
【００３７】
与えられている状態制約が充足される変更手順が存在しない場合、違反制約算出装置１００は、状態制約が充足される変更手順が存在するために緩和される状態制約、すなわち違反制約の部分集合を全て算出できる。
【００３８】
出力手段２００は、違反制約算出装置１００が算出した違反制約の部分集合を利用者に向けて出力する機能を有する。出力手段２００は、例えば表示装置である。
【００３９】
図１に示すように、本実施形態の違反制約算出装置１００は、手順生成手段１１０と、制約格納手段１２０と、極小集合格納手段１３０とを含む。
【００４０】
手順生成手段１１０は、変更計画を立案する機能を有する。手順生成手段１１０は、現在のシステム構成を変更目的のシステム構成へ変更するための変更手順を算出することによって、変更計画を立案する。
【００４１】
制約格納手段１２０は、状態制約を格納する機能を有する。図１に示す制約格納手段１２０内のc1,c2,c3,c4それぞれが、状態制約である。制約格納手段１２０に格納されている状態制約は、手順生成手段１１０が変更計画を立案する際に考慮することが求められる状態制約である。すなわち、本実施形態の制約格納手段１２０は、システムの構成変更の途中の状態であっても充足が求められる制約である状態制約を格納する。
【００４２】
極小集合格納手段１３０は、手順生成手段１１０が算出した違反制約の集合のうち極小集合を格納する機能を有する。図１に示す極小集合格納手段１３０内の{c2,c3}、{c2,c4}、{c3,c4}それぞれが、違反制約極小集合である。なお、図に示す{}は、制約の集合を表す。
【００４３】
また、図１に示すように、手順生成手段１１０は、構成制御手段１１１と、制約確認手段１１２と、違反制約格納手段１１３と、目的構成確認手段１１４と、違反制約集合追加手段１１５とを有する。
【００４４】
構成制御手段１１１は、システム構成の変更計画を立案するために、論理的にシステム構成を変更する機能を有する。すなわち、構成制御手段１１１は、システム構成の変更手順を生成するために仮想的にシステム構成を変更する。以下、構成制御手段１１１が構成した論理的なシステム構成を、論理システム構成と呼ぶ。
【００４５】
制約確認手段１１２は、構成制御手段１１１が仮想的に構成した論理システム構成が、制約格納手段１２０に格納されている状態制約を充足させるか否かを確認する機能を有する。
【００４６】
制約確認手段１１２は、仮想的に変更されたシステム構成において充足されない状態制約である違反制約を検出する。検出した後、制約確認手段１１２は、充足されない状態制約（違反制約）を違反制約格納手段１１３に格納する。
【００４７】
違反制約格納手段１１３は、違反制約を格納する機能を有する。図１に示す違反制約格納手段１１３内の{c2,c3}が、違反制約の集合である。
【００４８】
目的構成確認手段１１４は、構成制御手段１１１が仮想的に構成した論理システム構成が、変更目的のシステム構成であるか否かを確認する機能を有する。目的構成確認手段１１４は、仮想的に変更されたシステム構成が変更目的のシステム構成に到達したか否かを確認する。
【００４９】
違反制約集合追加手段１１５は、違反制約の極小集合を極小集合格納手段１３０に格納する機能を有する。違反制約集合追加手段１１５は、変更された論理システム構成が変更目的のシステム構成であると目的構成確認手段１１４が判断した時、違反制約格納手段１１３に格納されている違反制約集合を参照する。違反制約集合追加手段１１５は、論理システム構成が変更目的のシステム構成に到達した場合に、違反制約格納手段１１３に格納されている違反制約集合が極小集合であるか否かを確認する。
【００５０】
参照された違反制約集合が極小集合格納手段１３０に格納されている違反制約極小集合と同程度な極小集合である場合、違反制約集合追加手段１１５は、違反制約格納手段１１３に格納されている違反制約集合を極小集合格納手段１３０に格納する。
【００５１】
また、極小集合格納手段１３０に格納されている違反制約集合が参照された違反制約集合を包含する場合、違反制約集合追加手段１１５は、違反制約格納手段１１３に格納されている違反制約集合を極小集合格納手段１３０に格納されている違反制約集合と置き換える。
【００５２】
図６に示すような一般的な違反制約算出システムでは、制約集合ごとに手順生成手段が構成変更手順を生成する。しかし、本実施形態の手順生成手段１１０を構成する上記の各手段は、構成変更手順が生成される際に一度だけ違反制約集合を算出する。よって、本実施形態の違反制約算出システム１０は、図６に示すような違反制約算出システムに比べて違反制約極小集合をより高速に算出できる。
【００５３】
［動作の説明］
以下、本実施形態の違反制約算出装置１００の違反制約極小集合を算出する動作を図２を参照して説明する。図２は、第１の実施形態の違反制約算出装置１００による違反制約極小集合算出処理の動作を示すフローチャートである。
【００５４】
最初に、構成制御手段１１１は、変更計画を立案するために、論理システム構成を初期状態に設定する（ステップS101）。
【００５５】
次いで、構成制御手段１１１は、論理システム構成を全ての状態に変更済みであるか否かを確認する（ステップS102）。既に論理システム構成が全ての状態に変更された場合（ステップS102におけるYes）、違反制約算出装置１００は、違反制約極小集合算出処理を終了する。
【００５６】
未だ論理システム構成が変更されていない状態がある場合（ステップS102におけるNo）、目的構成確認手段１１４は、現時点での状態の論理システム構成が変更目的のシステム構成であるか否かを確認する（ステップS103）。
【００５７】
論理システム構成が変更目的のシステム構成である場合（ステップS103におけるYes）、違反制約集合追加手段１１５は、違反制約格納手段１１３に格納されている違反制約集合を取り出す。
【００５８】
取り出された違反制約集合が極小集合格納手段１３０に格納されている違反制約極小集合と同程度な極小集合であれば、違反制約集合追加手段１１５は、極小集合格納手段１３０に取り出された違反制約集合を追加する（ステップS109）。
【００５９】
なお、極小集合格納手段１３０に格納されている違反制約集合が取り出された違反制約集合を包含する場合、違反制約集合追加手段１１５は、極小集合格納手段１３０に格納されている違反制約集合を取り出された違反制約集合と置き換える。
【００６０】
次いで、構成制御手段１１１は、論理システム構成をバックトラックする（初期状態に戻す）（ステップS110）。バックトラックした後、違反制約算出装置１００は、再度ステップS102の処理を行う。
【００６１】
論理システム構成が変更目的のシステム構成でない場合（ステップS103におけるNo）、構成制御手段１１１は、現時点での状態の論理システム構成が取り得る次の構成が有るか否かを確認する（ステップS104）。
【００６２】
論理システム構成が取り得る次の構成が無い場合（ステップS104におけるNo）、構成制御手段１１１は、論理システム構成を１ステップ分戻すバックトラックを実行する（ステップS110）。バックトラックした後、違反制約算出装置１００は、再度ステップS102の処理を行う。
【００６３】
論理システム構成が取り得る次の構成が有る場合（ステップS104におけるYes）、構成制御手段１１１は、変更する次の構成を決定する。構成制御手段１１１は、該当するシステム構成操作を選択し、選択された操作に従って論理システム構成を１ステップ分変更する（ステップS105）。
【００６４】
論理システム構成が次の構成に変更された後、制約確認手段１１２は、制約格納手段１２０に格納されている状態制約が全て充足されているか否かを確認する（ステップS106）。格納されている状態制約が全て充足されている場合（ステップS107におけるYes）、違反制約算出装置１００は、再度ステップS104の処理を行う。
【００６５】
格納されている状態制約が１つでも充足されていない場合（ステップS107におけるNo）、制約確認手段１１２は、現時点での状態の論理システム構成で充足されていない状態制約、すなわち違反制約を検索する。制約確認手段１１２は、検索された違反制約を違反制約格納手段１１３に格納する（ステップS108）。格納した後、違反制約算出装置１００は、再度ステップS104の処理を行う。
【００６６】
本実施形態の違反制約算出装置１００は、全ての違反制約極小集合を高速に算出できる。一般的な違反制約算出装置では、充足対象の状態制約の組み合わせごとに生成される各部分集合に関して、手順生成手段が多くの計算時間を要する手順生成処理をそれぞれ実行していた。
【００６７】
本実施形態の違反制約算出装置１００の手順生成手段１１０は、変更手順を求めると共に違反制約も算出する。すなわち違反制約算出装置１００は、上述したように手順生成手段１１０を一回呼び出すだけで違反制約極小集合を全て算出できるので、一般的な違反制約算出装置に比べて違反制約極小集合を高速に計算できる。
【００６８】
［具体例］
以下、本実施形態の具体例を図を参照して説明する。本具体例における処理対象のシステム構成を図３に示す。
【００６９】
図３は、通信ネットワーク構成の例を示す説明図である。図３に示す通信ネットワークは、ゲートウェイ（ＧＷ）と、スイッチ（ＳＷ）Ａと、スイッチＢと、スイッチＣと、スイッチＤと、サーバａと、サーバｂとで構成されている。
【００７０】
図３に示すサーバａおよびサーバｂは、ゲートウェイを介して外部の通信ネットワークと通信可能に接続されたサーバである。外部の通信ネットワークとゲートウェイとの間には、d[Mbps]の通信トラフィックが流れている。また、サーバａとサーバｂでは、共通のサービスがそれぞれ稼働する。
【００７１】
また、図３に示す通信ネットワーク上のフローは、スイッチＡ、スイッチＢ、スイッチＣ、スイッチＤの各スイッチで通信経路を切り替えることができる。すなわち、図３に示す通信ネットワーク構成には、破線で表されているようにフローが４種類存在する。
【００７２】
図３に示す通信ネットワーク構成内のサーバａとサーバｂに対して、ファームウェアを更新するという変更計画を立案することを考える。ただし、ファームウェアの更新は、サーバが停止した後で行われる。本例では、変更手順が実行されている間の通信ネットワーク構成の全ての状態において、以下の状態制約c1〜状態制約c4を充足することが求められる。
【００７３】
c1：サーバは常に１台以上稼働
c2：ＧＷと停止しているサーバ（状態down）の間を流れる通信トラフィックは、停止しているサーバに到達できない
c3：サーバａが処理可能な通信トラフィックの量は、d/2[Mbps]未満
c4：サーバｂが処理可能な通信トラフィックの量は、d/2[Mbps]未満
【００７４】
例えば状態制約c2は、経路切り替えにより停止しているサーバに通信トラフィックをルーティングせず、稼働中のサーバに通信トラフィックを振り分けることを求める状態制約である。状態制約c2が充足されると、停止中のサーバへのアクセスを起因とするエラーが発生しない。
【００７５】
上記の４つの状態制約が全て充足されるような変更手順は存在しない。すなわち、状態制約c1〜状態制約c4が与えられたままの場合、変更計画は立案されない。よって、緩和されるとシステムの変更手順が生成され変更計画が立案されるような状態制約の集合のうちの極小集合を求めることを考える。
【００７６】
本例の場合、{c2,c3}、{c2,c4}、{c3,c4}のうちのいずれかの極小集合が緩和されれば、残りの状態制約を満たしながらサーバａとサーバｂの各ファームウェアのバージョンを更新できる変更手順が存在する。すなわち、本例における違反制約極小集合は、{c2,c3}、{c2,c4}、{c3,c4}の３つで全てである。以下、上記の違反制約極小集合を全て求める方法を説明する。
【００７７】
図４は、第１の実施形態の違反制約算出装置１００による探索の履歴の例を示す説明図である。図４に示す矩形は、論理システム構成を表す。
【００７８】
図４に示す最上段の矩形は、初期システム構成を表す。図４に示すように初期システム構成では、サーバａおよびサーバｂの各ファームウェアの現バージョンは、共にv.1である。また、スイッチＡとスイッチＣの間に通信トラフィックのフローが流れている。また、スイッチＢとスイッチＤの間に通信トラフィックのフローが流れている。
【００７９】
また、図４に示す各矩形間の矢印は、構成変更を表す。すなわち、図４に示す矢印は、構成制御手段１１１が論理システム構成を変更することを表す。
【００８０】
また、矩形内の下線が付された箇所は、変更前の論理システム構成から変更された箇所である。また、違反制約格納手段１１３を表す括弧（[]）内の下線が付された違反制約は、変更前の論理システム構成の状態から新たに追加された違反制約である。
【００８１】
以下、図３も参照して、本例における違反制約算出装置１００による違反制約極小集合算出処理を具体的に説明する。最初に、構成制御手段１１１は、論理システム構成として初期システム構成を用意する（ステップS101）。図４に示す最上段の矩形が、用意された論理システム構成（初期システム構成）を表す。
【００８２】
初期システム構成が用意された時点では、論理システム構成は、未だ全ての状態に変更されていない（ステップS102におけるNo）。また、初期システム構成は、変更目的のシステム構成ではない（ステップS103におけるNo）。
【００８３】
次いで、構成制御手段１１１は、初期システム構成が取り得る次の論理システム構成が存在するか否かを確認する（ステップS104）。図４に示すように、初期システム構成が取り得る次の論理システム構成を表す４つの矩形が、上から２段目に存在する。すなわち、初期システム構成が取り得る次の論理システム構成は存在する（ステップS104におけるYes）。
【００８４】
次いで、構成制御手段１１１は、次の論理システム構成を、例えば図４に示す上から２段目の最も左の矩形が表す論理システム構成に決定する。構成制御手段１１１は、初期システム構成を次の論理システム構成に変更するために、仮想的にサーバａを停止（サーバa=down）させる（ステップS105）。
【００８５】
次いで、制約確認手段１１２は、制約格納手段１２０に格納されている状態制約c1〜状態制約c4のうち、変更された論理システム構成で充足されていない状態制約を調べる（ステップS106）。
【００８６】
調べた結果、制約確認手段１１２は、「ＧＷと停止しているサーバ（状態down）の間を流れる通信トラフィックは、停止しているサーバに到達できない」という状態制約c2が、サーバａに関して充足されていないことを確認する（ステップS107におけるNo）。次いで、制約確認手段１１２は、違反制約格納手段１１３に状態制約c2を追加する（ステップS108）。
【００８７】
上記のように構成制御手段１１１は、図３に示すシステムが取り得る論理システム構成を次々に探索する。探索の方法として、例えば幅優先探索や、違反制約格納手段１１３に格納されている違反制約の集合の包含関係における最優良探索が用いられる。また、幅優先探索や最優良探索以外の様々な方法が探索の方法として用いられる。
【００８８】
例えば、探索中に論理システム構成が、図４に示す上から３段目の左から２番目の矩形が表す論理システム構成に変更されたとする。変更された論理システム構成ではサーバａとサーバｂが共に停止しているため、「サーバは常に１台以上稼働」という状態制約c1が充足されていない。
【００８９】
また、「ＧＷと停止しているサーバ（状態down）の間を流れる通信トラフィックは、停止しているサーバに到達できない」という状態制約c2も両方のサーバに関して充足されていない。よって、制約確認手段１１２は、{c1,c2}を違反制約集合と判断する。
【００９０】
図４に示すように違反制約格納手段が[c2]であるため、遷移元である上から２段目の最も左側の矩形が表す論理システム構成の状態での違反制約格納手段１１３には、状態制約c2のみが格納されている。制約確認手段１１２は、違反制約格納手段１１３に違反制約集合と判断した{c1,c2}を追加する。すなわち、違反制約格納手段１１３には、{c1,c2}が格納される。
【００９１】
上記のような探索が続けられた結果、図４に示す最下段の最も左の矩形が表す論理システム構成まで論理システム構成が変更されたとする。変更された論理システム構成では、サーバａおよびサーバｂの各ファームウェアのバージョンは、共に更新バージョンであるv.2に変更されている。
【００９２】
また、スイッチＡとスイッチＣの間に通信トラフィックのフローが流れている。また、スイッチＢとスイッチＤの間に通信トラフィックのフローが流れている。すなわち、ゲートウェイからサーバＡに通信トラフィックのフローが流れており、ゲートウェイからサーバＢに通信トラフィックのフローが流れている。よって、変更された論理システム構成は、変更目的の論理システム構成である（ステップS103におけるYes）。
【００９３】
次いで、違反制約集合追加手段１１５は、現時点で違反制約格納手段１１３に格納されている違反制約集合{c2,c3}を、極小集合格納手段１３０に追加する（ステップS109）。ただし、違反制約集合{c2,c3}が包含する違反制約集合が既に極小集合格納手段１３０に格納されている場合、違反制約集合追加手段１１５は、違反制約集合{c2,c3}を極小集合格納手段１３０に追加しない。
【００９４】
また、違反制約集合{c2,c3}を包含する違反制約集合が既に極小集合格納手段１３０に格納されている場合、違反制約集合追加手段１１５は、格納されている違反制約集合を違反制約集合{c2,c3}に置き換える。
【００９５】
また、違反制約集合{c2,c3}が極小集合格納手段１３０に格納されている違反制約極小集合と同程度な極小集合である場合、違反制約集合追加手段１１５は、違反制約集合{c2,c3}を極小集合格納手段１３０に追加する。例えば、両方の集合に含まれている要素が同数である場合、違反制約集合追加手段１１５は、違反制約集合{c2,c3}を極小集合格納手段１３０に追加する。
【００９６】
違反制約集合が追加された後、構成制御手段１１１は、論理システム構成をバックトラックし、他の論理システム構成を探索する。上記の処理が繰り返し実行されることによって、全ての論理システム構成の探索が完了する（ステップS102におけるYes）。すなわち、違反制約算出装置１００は、違反制約極小集合算出処理を終了する。
【００９７】
図４に示すように、本例では全ての論理システム構成の探索が完了すると、{c2,c3}、{c2,c4}、{c3,c4}の３つの違反制約極小集合が極小集合格納手段１３０に格納される。出力手段２００は、例えば、極小集合格納手段１３０に格納されている３つの違反制約極小集合{c2,c3}、{c2,c4}、{c3,c4}を、利用者に向けて表示する。
【００９８】
［効果の説明］
本実施形態の手順生成手段１１０は、システム構成の変更手順を生成する機能を有する。手順生成手段１１０は、仮想的にシステム構成を変更する構成制御手段１１１と、仮想的に変更されたシステム構成において充足されていない状態制約である違反制約を検出する制約確認手段１１２と、検出された違反制約を格納する違反制約格納手段１１３とを有する。
【００９９】
また、手順生成手段１１０は、仮想的に変更された構成が変更目的である構成に到達したか否かを確認する目的構成確認手段１１４を有する。また、手順生成手段１１０は、論理システム構成が変更目的である構成に到達した場合に違反制約格納手段１１３に格納された違反制約集合が極小集合であるか否かを確認し、極小集合であれば極小集合格納手段１３０に追加する違反制約集合追加手段１１５を有する。
【０１００】
図６に示す違反制約算出装置９００では、制約制御手段９１０が状態制約の集合を基に生成される部分集合ごとに手順生成手段９３０を起動させ、起動する度に手順生成手段９３０がシステム構成を変更する手順を生成する。変更手順の生成処理は計算時間が長い処理であるため、違反制約算出装置９００は、全ての違反制約極小集合の算出に多くの時間を要する。
【０１０１】
しかし、本実施形態の手順生成手段１１０は、上記のようにシステム構成の変更手順を生成する処理の中で違反制約極小集合を求めるように構成されている。よって、本実施形態の違反制約算出装置１００は、図６に示す違反制約算出装置９００に比べて、全ての違反制約極小集合を高速に求めることができる。
【０１０２】
なお、本実施形態の違反制約算出装置１００は、例えば、記憶媒体に格納されているプログラムに従って処理を実行するCPU(Central Processing Unit)によって実現される。すなわち構成制御手段１１１、制約確認手段１１２、目的構成確認手段１１４、および違反制約集合追加手段１１５は、例えば、プログラム制御に従って処理を実行するCPUによって実現される。また、違反制約算出装置１００は、GPU(Graphics Processing Unit)等の、CPU以外のプロセッサによって実現されてもよい。また、違反制約算出装置１００は、データ処理装置でもよい。
【０１０３】
また、違反制約格納手段１１３、制約格納手段１２０、および極小集合格納手段１３０は、例えばRAM(Random Access Memory)で実現される。
【０１０４】
また、本実施形態の違反制約算出装置１００における各部は、ハードウェア回路によって実現されてもよい。一例として、構成制御手段１１１、制約確認手段１１２、違反制約格納手段１１３、目的構成確認手段１１４、違反制約集合追加手段１１５、制約格納手段１２０、および極小集合格納手段１３０が、それぞれLSIで実現される。また、それらが１つのLSIで実現されていてもよい。
【０１０５】
次に、本発明の概要を説明する。図５は、本発明による違反制約算出システムの概要を示すブロック図である。本発明による違反制約算出システム１０は、変更対象のシステムの構成要素の状態を仮想的に変更することによって変更対象のシステムの構成を変更目的の構成まで仮想的に変更する変更手段１１（例えば、構成制御手段１１１）と、仮想的に変更される構成要素の状態に課される制約のうち充足されていない制約である違反制約を変更対象のシステムの構成が仮想的に変更されている間に算出する算出手段１２（例えば、制約確認手段１１２）とを含む。
【０１０６】
そのような構成により、違反制約算出システムは、違反制約極小集合の算出にかかる時間を削減できる。
【０１０７】
また、違反制約算出システム１０は、算出された違反制約の集合のうち他の集合を包含しない集合である極小な集合を記憶する記憶手段（例えば、極小集合格納手段１３０）を含んでもよい。
【０１０８】
そのような構成により、違反制約算出システムは、違反制約の極小集合のみを算出結果として利用者に提示できる。
【０１０９】
また、算出手段１２は、変更対象のシステムの構成が変更目的の構成まで仮想的に変更された時点で算出された違反制約の集合と記憶手段に記憶されている違反制約の極小な集合とを比較し、記憶されている違反制約の極小な集合に含まれている要素と同じ数の要素が含まれている算出された違反制約の集合を記憶手段に追加してもよい。
【０１１０】
そのような構成により、違反制約算出システムは、複数の違反制約極小集合を提示できる。
【０１１１】
また、変更手段１１は、変更対象のシステムの構成が変更目的の構成に仮想的に変更されるまでの変更対象のシステムの構成要素の状態を仮想的に変更する複数の手順ごとに変更対象のシステムの構成を変更してもよい。
【０１１２】
そのような構成により、違反制約算出システムは、全ての違反制約極小集合を算出できる。
【０１１３】
また、仮想的に変更される構成要素の状態に課される制約は、システムが仮想的に変更されている間、常に充足が求められる制約（例えば、状態制約）でもよい。また、違反制約は、変更前のシステムの構成、変更中のシステムの構成、または変更後のシステムの構成のいずれかで充足されない制約でもよい。
【０１１４】
また、違反制約の集合は、システム構成を変更する変更手順が存在しない場合に緩和されると変更手順が存在するような集合でもよい。
【０１１５】
また、違反制約算出システム１０は、仮想的に変更されたシステムの構成が変更目的の構成であるか否かを確認する確認手段（例えば、目的構成確認手段１１４）を含んでもよい。
【０１１６】
また、違反制約算出システム１０は、制約を格納する制約格納手段（例えば、制約格納手段１２０）と、算出された違反制約を格納する違反制約格納手段（例えば、違反制約格納手段１１３）とを含んでもよい。
【産業上の利用可能性】
【０１１７】
本発明は、ICT(Information and Communication Technology)システムの構成を変更する手順を生成する用途に好適に適用される。
【符号の説明】
【０１１８】
１０  違反制約算出システム
１１  変更手段
１２  算出手段
１００、９００  違反制約算出装置
１１０、９３０  手順生成手段
１１１  構成制御手段
１１２  制約確認手段
１１３  違反制約格納手段
１１４  目的構成確認手段
１１５  違反制約集合追加手段
１２０、９２０  制約格納手段
１３０、９７０  極小集合格納手段
２００  出力手段
９１０  制約制御手段
９４０  手順存在確認手段
９５０  極小違反集合追加手段
９６０  制約全体集合格納手段
【図１】
2018120457.tif 000003
【図２】
2018120457.tif 000004
【図３】
2018120457.tif 000005
【図４】
2018120457.tif 000006
【図５】
2018120457.tif 000007
【図６】
2018120457.tif 000008
【図７】
2018120457.tif 000009