アルゴリズム３ ソフトCardinality制約の改善

 Cardinalityとは、数を数える制約のことです。基数制約とか不等式制約とか、言い方の変遷がありますが、皆同じです。制約の範疇を分けるものとして、

Cardinalityか、NonCardinalityかの２種類があります。

■Cardinality　　　ー数を数える制約

■NonCardinality　ーブール演算制約

一般に数理ソルバの制約は、全てCardinalityで記述されます。従い、数理ソルバは、Cardinality制約が得意です。というより、数理ソルバは、Cardinality制約でしか記述できません。ブール演算は得意ではありません。一方アルゴリズム１系のソルバは、ブール演算が得意で、Cardinality制約は苦手です。Cardinalityのスケジュールナースの特徴は、常に、許容範囲というソフト範囲が明示されていることです。ソフト範囲が限定されて、ある値を境にハード制約になる、というのは、恐らくは、スケジュールナースユニークであり、他のソフトでは扱わないと思います。便利な反面、初心者には、とっつきにくく,これで苦労された方も多いのではないでしょうか？実は、ブール演算で、数を数えようとすると、必然になるのですが、これについては、別の機会に。

余談ですが、情報は全て0/1だけで表現できることを示したのは、シャノンという学者です。0/1が最もプリミティブな表現です。そこから出発するのがブール演算です。なので、数を数えるということもブール演算で表現可能です。つまり、コンピュータの動作の最も基礎は、０/1であり、その合成集合は、AND/NOT/ORの３つのブール演算オペレータでどんなものでも合成出来ます。

一方、制約は、２種類しかありませんという話はよくします。一つは、ハード制約、もう一つはソフト制約です。

数理表現への橋渡しは、グラフ理論上のグラフになります。制約理論で言えば、リソース制約下の最小パス問題(RCSPP)、になります。実装という観点でみると、下のような難易度になります。

                    　 ｜　Hard　 |   　Soft

ーーーーーーーーーーーーーーーーーーーーーー

Cardinality　　　｜　　難　|　　超難

NonCardinality　｜　　超簡単　|　　簡単　　　　

つまり、Soft　Cardinalityの実装は超難しいのです。上のHard　Cardinality制約については、2022年に特許化しましたが、そのときは、Soft Cardinalityについては解決していませんでした。

今回INRC2の難問を解くに当たって、副産物として出てきたのは、このSoft Cardinalityに対するアルゴリズムです。

未だ解けてはいないし、改善も進行中なのですが、ドラスティックな変化があるので、中間報告しておきます。

下は、池上ベンチをアルゴリズム３現行スケジュールナースで解いた様子です。

アルゴリズム１は、数秒で解けるのに対して、このように時間がかかっているのは、Soft　Cardinalityのコンパイルに時間がかかっているからです。

それが、現在開発中のソルバでは、

となっています。これは、Soft　Cardinalityのコンパイル時間を削減出来たからです。（それでもこの問題に対してAL1の優位は変わりませんが。）

例えば、多数のCardinlaityがScheduling　Benchmarks　Instance13では記述されていますが、これを全てソフト制約にした場合は、現行スケジュールナースではコンパイル出来ません。しかし、この技術を使うとコンパイル出来るようになります。数理ソルバに取り組んで以来、長年の研究によりようやく満足できる性能を発揮できるようになりました。

これにより、数理ソルバを用いて解ける可能性が高まることを意味します。Al1/3共、各々得意な領域はあるのですが、使用比で、現状100:1から100:10位になる位になるのではないかと思います。特に厳密解を知りたい場合に有用になる筈です。

また、Al1とAl3を融合した万能ソルバも視野に入っています。これにより最終目標である、常に厳密解にもっとも近い解を示すアルゴリズムを提示できる可能性が高まりました。

アルゴリズムというのは、問題の解き方です。ソフトウェアの基礎になります。分岐とループ(IF文、For文）さえあれば、何でも処理できるを示したのは、チューリングという学者です。

NSPに関して、このアルゴリズムを使えば、常に最適もしくは、最も最適に近い解が得られる、というのは分かっていません。というか、そもそもNP困難なのでそれを示すことは不可能であろうと思いますが、実用的な意味で、今後数十年は使えるアルゴリズムを示せたらそれは、NSPにおいてプリミティブな事だろうと思います。