祝日のシフト

カレンダー上の祝日休みは、公休をつけるのではなく祝日(シフト)としたい。

というご要望がありました。祝日は、公休ではなく、次のような場合連続勤務とカウントするようにしたいとのことです。


例①
7月21日　入り
7月22日　明け
7月23日　祝（日勤扱い）
7月24日　祝（日勤扱い）
7月25日　公休
となり、もし20日が日勤であれば19日は必ず休みになります。（20日から24日で5連勤
となるため）

例②
7月22日　入り
7月23日　明け
7月24日　祝（日勤扱い）
7月25日　公休
ここで、日勤扱いとしていますが、ユーザの真の要求は、公休でない勤務が連続6日あってはいけないというこです。（惑わされてはいけません。祝を日勤集合のなかに入れてしまうと、列制約もおかしくなってしまいます。） ✓公休　の意味は、公休でない＝公休以外のシフト　になります。
これを使うことによって、一々集合定義する手間が省けます。

要は、今までの

A)明け　→公休

という制約を
A’）明け　→公休　または　祝

という制約にすればよいことが分かります。ですので祝というシフトを追加することにします。
また「公祝」という公休または祝　集合シフトを作ります。

次に祝というシフトの要件を考えます。
B)祝日　：祝が存在できる　　公休は、存在してはならない
C)祝日以外:祝は存在してはならない　公休は、存在できる


従って、AをA'に変更、B,Cを記述追加をすればよいことになります。

制約は、以上ですが、祝日というは曲者で、カレンダ上の祝日が必ずしもその病院での祝日ではないというケースも想定されます。そこで、ユーザ祝日を年間で定義しておくとよいでしょう。

探索プログラム改善

どうも思うように解が出てこないので、さらに一工夫することにしました。前回、探査木のROOT付近では、BFSある程度depthが深くなったところでDFSにする話をしました。切り替え境界のdepthが深ければ深いほど、よりOptimumに近づくと考えられます。理想を言えば、BFS中にInteger解が得られたらそれがBestです。なので、同じ時間内で、もっとdepthを掘ることを考えます。そのためには、同じdepth中のtop Kだけを取ります。言い換えると、その時点の質のよいエリートだけを対象とします。その時点で出来がよくないのは、将来（ボトム方向に下降したときに）劇的改善は見込めないだろう、亀は兎を追い越せないだろう、という発想です。

こうすることで、厳密LBではなくなってしまいます。推定LBとなってしまう代わりに、下位depthにおいて、OptimumなObj付近を効率よく探索できるということです。Shiftsが7だと、全組み合わせは、7**depth　となり高々depth30程度でも１e25程度の空間となります。Instance15で、Interger解が得られているのは、現在のところdepth 140付近です。

MaxSAT2020案内が届きました。

今年は、SAT　conferenceがオンライン開催になったので、MAXSATもそうだと思います。
今年は、新しいカテゴリとして、TOP　Kというのが創設されました。元々、OR系であったので、
その類型だと思います。

Dear all,
The MaxSAT Evaluation 2020 is coming up soon!
We have extended the deadline for submitting benchmarks and solvers
for the MaxSAT Evaluation 2020 to Friday, June 12, 2020.
The final version of your solver must be uploaded to the following
subspaces (depending on the category you want to participate):
- MSE2020->Evaluation->Complete->Unweighted
- MSE2020->Evaluation->Complete->Weighted
- MSE2020->Evaluation->Incomplete->Unweighted
- MSE2020->Evaluation->Incomplete->Weighted
- MSE2020->Evaluation->TopK->Unweighted
- MSE2020->Evaluation->TopK->Weighted
More details on the final submission are available at:
https://maxsat-evaluations.github.io/2020/submission.html
We have a new track this year to enumerate the top-k solutions. We
encourage you to submit to this track if you can change your current
algorithm to support the enumeration of solutions. More information
about this track is available at:
https://maxsat-evaluations.github.io/2020/topk.html
So far we did not receive many new benchmarks. If you are using MaxSAT
to solve problems, we encourage you to submit your formulas to this
year's MaxSAT Evaluation. New benchmarks are critical for the
continuous improvement of MaxSAT solvers and to perform a better
assessment of their performance.
Best regards,
The MaxSAT 2020 organizers

新解探索プログラム

SchedulingBenchmarkサイトで、解の更新がなされ、手持ちの新解は、全て発見されてしまいました。可能性が残っているのは、Instance15のみです。そこで、新解を発見できなくてもLBの更新を目指すことにしました。現在LBは、3823がKnown Best値となっており、3827が現在、私が持っている結果です。この時点で報告してもよいのですが、残念ながらEvidenceがありません。

計算機を廻すのは、一週間以上を想定します。次のStarategyでLBの更新を狙います。

１）DFS→ルート周りはBFSに変更


これで、少なくともLBが更新できると思います。今までは、DFS一辺倒だったのですが、LBを更新するとなると、全ての探索木で、LB以上となる証明が必要となります。そのためには、DFSではなく、BFSが必須です。しかし、全部をBFSにすると爆発して一生、Feasibleな解は見つかりません。なので、ある程度以上のdepthでは、DFSとします。これで、LBの更新と、それまでのBest解の両方を作戦です。一度限りのプログラムなので、Ifdefで作成しました。


２）部分的に問題そのものを緩和
問題を簡単にすれば、自動的にLBも下降します。しかし、そのLBがKnownBest以上である限りにおいては、LBを求める意味はあります。問題が緩和されたLBは、緩和される前のLBよりも確実に小さくなるはずです。つまり問題が緩和されたLBは、元の問題のLBとして担保できます。
しかし、注意しなければならないのは、得られた解が、元の問題上でのFeasibleな解には必ずしもならない、ということです。こうまでして緩和を行うのは、探索速度の向上が期待できるからですが、これは、問題構造を熟知しているからできることであって、汎用手段ではありません。なりふり構わず新LBを得ようとしています

略語の説明

DFS：Depth　First　Search
BFS:Breadth　First　Search
LB:　Lower　Bound

Visual C++2019での挙動差異

Algorithm4のインスタンスの一部が動きませんでした。
調べたところ、
次の箇所、std::mapの挙動が違いました。
mapがemptyであるとき、0が入ると思っていたのですが、デバッグモードでは、0、最適化(Release Mode)を行うと、1が入ってしまいました。

  map[xx]=map.size();
  

言語仕様上、正しい動作は分からないのですが、とりあえず、明示的に次のような対処を行いました。

　int size=map.size();
  map[xx]=size;
  

Runtime自体は、変わっていないようですので、恐らくコンパイラの差異なんでしょう。いつものことですが、コンパイラを変えると何かしら、こうした問題が発生します。

各国祝日の調査

AWS対応は、ほぼCodingが終わりました。
後は、Docker　SDK提供とIAM　Role/Principal等のインタフェース定義対応が残るのみです。

SC3のデスクトップブリッジ対応は、海外から始めようと思います。

そうなると問題は、

１）英語マニュアル
２）ソフトの各国対応

になります。中でも祝日定義をどこから拾ってくるか問題です。

WindowsでAPIであればよいのですが、UWPでもなく、方法としては、次の二つになるかと思います。

１）https://qiita.com/richmikan@github/items/9090407e3ab9cd3e80b2
２）https://hnw.hatenablog.com/entry/2019/04/13/212054

１）は、オンライン　２）は、オフラインになります。要検討です。デスクトップブリッジは、ネットアクセスを許容すると思うので、１）が第一候補です。

とりあえず、SC3日本語マニュアルを作ります。

SC3のプロモーション動画を作りました

3交代正循環を題材にして動画をSC3で作ってみました。

https://youtu.be/0vuGpXbO2Wc

AVIをそのままアップロードしましたが、文句を言われませんでした。