2022年9月30日金曜日

ペア制約に関する一考察

 スケジュールナースのペア制約は二つの種類があります。

1)禁止

2)AならばB

です。たとえば、Aの夜勤入りとBの夜勤入りが同じにならないように禁止する制約が1)になります。反対にAの夜勤入りとBの夜勤入りが常に同じく入る(プリセプタ・プリセプティ)の場合は、2)を両方向に適用します。つまり、

3A)Aが夜勤入りならBも夜勤入り A→B

3B)Bが夜勤入りならAも夜勤入り B→A

これで、プリセプタプリセプティの関係A==Bは出来ます。

証明:

(!A|B)&(A|!B)=!(A&!B)& !(!A&B)=!C&!D=!(C|D)=

=!(A^B)=A==B (同値、XORの否定)


 



 

<問題の難易度>

探索空間と解空間の話は前にしましたが

、禁止の場合は、それほど解空間は狭まらないと考えられます。実際、かなりの数のペアをハード禁止しても、解がないということは殆ど経験しません。

禁止は、OR的アプローチだと、A+B<=1

という表現が出来ます。各スタッフを独立の問題と捉えたとき、各Day列は、各スタッフの線形和制約となりますが、これと同じ種類の普通の制約の一種に過ぎないということです。なので、いかに多くのペア禁止制約があろうと、厳密解を求めるのに支障はありません。


ところが、A→Bは、かなり解空間を狭めます。A→Bは、Implicationとも呼ばれ、そのブール式は、!A+Bとなります。AがTrueであれば、BがTrueであることを強要されることになります。これは、AとBの間に強固な結びつきを強いることになります。ペア制約がなければ、通常は、上で述べたような線形和の制約しかありません。つまり、スタッフ毎の制約は、各々スタッフ内で閉じており、各々独立したグラフで表現できます。スタッフ毎の閉じたグラフを線形和で緩く結んだ関係になっており、線形ソルバが得意とするところの関係に持ち込めます。スタッフ毎の制約がいかに複雑であっても閉じた各スタッフについては、閉じたグラフとなります。

A→Bが無ければ、各スタッフ固有の閉じたグラフに出来る。ソフト基数制約が入ると下のように複雑になるが、閉じた系であることに変わりはない。





ところが、A→Bが一つでもあると問題は複雑です。各スタッフを閉じた系として処理できなくなってしまうのです。複数のグラフをマージしようとすると指数関数的に複雑になり、多くの人が関われば、爆発してThe Endとなります。

このことは、実務的には、よく遭遇する問題ではありますが、国際学会含めて、これを議論したPaperは見たことがありません。海外では、そのような要求がそもそもないのかは分かりませんが、簡単なペア禁止も含めて制約を見たことがありません。(日本では、プリセプタプリセプティは、ありますし、誰々さんと誰々さんが一緒に仕事をするのは嫌だ、という要求はよく遭遇あります。)

理論的解析は、困難です。A→Bの二人に限れば、なんとか厳密式を書くことが出来ると思いますが、それ以上は極めて困難です。ただ言えることは、解空間はかなり狭められる、ということだけです。プレセプタプリセプティの場合、解が存在しない確率はかなり高いです。なので、ハード制約ではなくソフト制約化が必須となります。

で、A→Bは、AL3はとても苦手です。一方禁止は上で述べたように線形ソルバにとっては、普通の制約なので、厳密解を得るのに障害になるとは考え難いです。なんとかA→BをAL3上で改善する方法を考えたのですが、やはり実装が難しい、というところで止まっています。改善策は、多分、存在すると思いますが。

とりあえず、現状A→Bがある場合は、AL1択です。(10人未満ならAL2もアリです)。新人が二人以上いたら、ベテラン何人以上みたいな制約がある場合は、AL1を選択してください。

A→B制約下で、厳密解を導くことは、極めて困難である、ということだけ記しておきます。





2022年9月24日土曜日

HiGHSがSCIP並みに

 HiGHSの性能向上が著しく、現時点でSCIP並みになっていると思われます。

こちらは、定番Visualizations of Mittelmann benchmarks | Interactive plots showing pairwise time differences for every instance and every solver (mattmilten.github.io)

ベンチマーク結果です。

NSPに関しては、SchedulingBenchmarksをInstance8まで行ってみました。Highs Versionは、最新ソース1.22+α(改修済みVersionです)



驚くべきことにinstance7まで厳密解が得られています。instance8では、feasibleな解(実行可能解)が3600sec行っても得られていませんが、CBCと比較してみれば、オープンソルバとしては、素晴らしい結果であることが判明すると思います。

(現在世界最速と思われるスケジュールナースⅢAlgorithm3が59secで厳密解を証明しているのは、例外的な速さです。instance8は、Gurobiでも10分以上、Cplexで一時間以上を要すると思います。)

では、どうしてあのような少ない行数でハイレベルな結果が得られているか?ソースを眺めたのですが、良く分かりませんでした。特別なCutやBranching、Heuristicsを行っているように思えませんでしたし、Presolverは、多分SCIPに同じです。恐らくは、Domain Propagationが効いているのではないか?ということです。Domain Propagationは、比較的新しい技術で、MIPソルバ内にSATソルバもどきがあるようなものです。SCIPの中身は、こちらが詳しい

https://imi.kyushu-u.ac.jp/~3rd_imi_ism_zib_ws/SCIP.pdf

また、マルチスレッド化の実装は、現在中途だと思うので、今後も性能向上は期待できると思います。

Algorithm2では、HIGHSによる実装になりますが、NSPに関しては、極小さい規模を除いて依然として皆様の使用には耐えません。逆に言えば、それだけNSP(探索空間が極めて広い問題分野)は難しいということでもあります。

しかし、現在シリーズでアップしているシフトが決まっておりタスクの最適化を行う問題(4直2交代等)では、十分に実用的です。(どの問題分野が得意かということは、ソルバによって異なります。この種の、行方向の自由度が狭い問題においてMIPソルバは有効です。)今後インタフェースがより強化されると思うので、もう少し使いやすい形態(実行途中のfeasible解の表示等)になると期待されます。


なお、上記搭載は、Al2として次回リリース時から適用になります。


2022年9月21日水曜日

158以前で求解した解を159A以上のVersionで予定へ送ることが出来ない

 という事象が報告されています。本現象は、159より前のVersionとそれ以後で発生し、シフト解では起こりません。


本現象は、159Aで再求解すれば、解決します。以降、問題は生じません。

(タスク予定に送るには、タスク解を開いて、送ってください。シフト解から送ると、タスク予定に送れないことがあります。)


再求解により解が微妙に変化することを嫌う場合には、次のように解をコピペして予定に貼り付けることでも対応できます。


<原因>

159Aで内部時刻フォーマットを変更したため、それ以前のフォーマットと互換が取れなくなってしまったものです。

2022年9月17日土曜日

Excel出力時のMinor Flaw

 Excel出力時にlabelではなく、タスク名が出力される場合がありました。本現象は、違うタスク名に同じラベルが割り当てられているときに発生します。

次の例では、DummyとDummyDayに同じラベル・が割り当てられています。

この場合に、ラベル名ではなくタスク名が出力されてしまいます。 

workaroundとしては、ラベル名を異なるものに変更することにより解決できます。例えば、全角の・と半角のそれにすれば、見た目はほぼ同じですが違うラベルと認識されます。
または、Versionを160AにVersionUpすることで解決します。





2022年9月15日木曜日

Kissat失敗

 CNFでは、圧倒的な性能を見せるも、最適化問題では、全く性能が出ませんでした。

残念なことに、改善傾向は見られず、現行ソルバにも劣るという結果になりました。現行ソルバもVersionが上がればそれに伴い、なにがしかの改善が期待したいところですが、こちらも、どちらかと言えば退行している印象です。

結論的には、IntelのNadalさんが指摘した通りの結果となってしまいました。この一見不可思議な現象の指摘は、2021年からあります。

kims-sat21-preprint.pdf (alexeyignatiev.github.io)

上で試せていないkissatならば..という期待を抱いて、改修してみたのですが散々な結果に終わりました。

ということで、Algorithm1をReplaceする計画はドロップします。



2022年9月14日水曜日

KissatのWindowsポート

KissatをWindowsにポートしました。

LinuxソースからWindowsソースに変更するのは、結構面倒です。

鬼門は、5 つあり、

bool 、rnd()、構造体サイズ,配列宣言,Linux特有のライブラリです。VisualC++ の構造体中 boolのBitfieldの扱いがGCCと異なること。rnd()は、メルセンヌ・ツイスタに変更すること。パックド構造体は、#pragmaを使用すること、配列宣言は、_allocaに変換することにより対応しました。