RCSPの一般解法 ラベル設定法

 この解法は、グラフ中に複数の累計状態（パレート）を維持することにより求めるものです。

私は、これまで実装したことがなかったのですが、計算量の見積もりのために、実装してみることにしました。

この解法で、必要になる概念は、下記の二つです。

■ラベル

■Dominate　支配する

ここで、ラベルというのは、累計状態を指す、用語です。今グラフがあるとします。

複数の累計制約があると、各ノードには、複数の累計状態を覚えている必要があります。たとえば、次は、インスタンス13のグラフ状態のデバッグStateです。グラフの要素数は、1711個、ラベルの総数は、534万個、一つのグラフノードで最大のラベル数が18204個であることを示しています。最初の値は、コストで、次の値は、累計状態を表しています。同じコストではあっても、ちょっとずつ累計状態が変わっていることが分かります。

Graph Elements=1711  Label Sum=5348323 Max labels per Node=18204

\tcost=12.0111 67,0,6,2,1,0,0,0

\tcost=12.0111 67,0,5,2,2,0,0,0

\tcost=12.0111 68,0,8,2,0,0,0,0

\tcost=12.0111 68,0,5,1,3,1,0,0

\tcost=12.0111 68,0,6,1,2,1,0,0

\tcost=12.0111 68,0,7,1,1,1,0,0

\tcost=12.0111 68,0,8,1,0,1,0,0

\tcost=12.0111 67,0,5,1,4,0,0,0

この一つ一つの行がラベルという呼称になります。ラベルというのは、最適値を得るために区別が必要な（最小限度の）状態名の呼称です。

グラフエッジをたどることによって、次のノードへと移行していき、最終的には終端します。終端での累計状態が、元々の不等式[最大、最小]にマッチしていれば、feasibleな解となり、マッチするものがなければ、infeasibleとなります。feasibleな解のうち最小のものを最適値とすることができます。

終端に辿り着くまで、その累計制約を満たすかどうかは、一般には分かりません。直前の状態ならば、明らかに満たさないということは分かりますが、中間点、例えば上記のノード状態で、終端時にどのように累計状態が成長するかは、分からないので、とにかく状態を維持して終端まで進むしかありません。

累計制約の本数が多いと、容易に爆発します。如何に状態、ラベル数を少なくできるか？がこの方式のポイントです。状態を少なくすることを枝刈り(pruning)と呼んでいます。

インスタンス13では、8本程度の累計制約があるのですが、すでにこの段階で、枝刈りなしには、reasbleな時間内に解くことはできません。