Q.夜勤の際に、特定の人間との夜勤の回数を一回以下にしたいのですがどのようにすればよろしいでしょうか。

 Ans.

似た実装として例として、以下があります。

https://schedule-nurse.blogspot.com/2024/04/q_14.html

題意は、特定のスタッフとそれ以外との夜勤ペア回数を最大１回にしたいということですが、

これは、日々の列制約（全てのペア組み合わせ）に対して、行制約＝今月期間中に最大１回と、列と行の複合制約となります。こうした複合制約については、Pythonでしか書けません。

以下は、プロジェクトを走らせた様子です。解がない可能性がありますので、

■ソフト制約にする（ソフトレベル設定で、適用と重みを設定）

することと、言語制約にチェックを入れることが必要です。

スタッフプロパティシートで、ペア回数を最大１回にするスタッフを設定します。

上のメニューにするためのグループ定義記述です。

解になります。ペア回数を最大１回にしたところのスタッフは、全スタッフに対して最大１回にソフト制約されます。

このように、Python記述をブラックボックスとして、将来に渡る変更は、スタッフプロパティシートで吸収できるようにするのが、良い実装です。スタッフ個別名を用いていない点に注意してください。

実装は、以下となります。Python記述は、ブラックボックスとして扱えるように記述しています。（僅か十数行です。”夜勤”の部分をご自分のプロジェクトのシフト名に入れ替えれば汎用的に使える記述です。）

import sc3


def ペア回数制限Sub(person1,person2):
    if person1==person2:#同じ人は制約しない
        return
    list=[]
    for day in 今月:
        v1=sc3.GetShiftVar(person1,day,'夜勤')
        v2=sc3.GetShiftVar(person2,day,'夜勤')
        list.append(v1&v2)
    s=staffdef[person1]+"と"+staffdef[person2]+"の組み合わせ回数"
    print(s)
    sc3.AddSoft(sc3.SeqError(0,1,3,list),s,5)#min max allowable errors 最大1回に制限

def ペア回数制限():
    for 特別person in 夜勤ペア最大１回:
        for person in 全スタッフ:
            ペア回数制限Sub(特別person,person)

ペア回数制限()

超大規模問題に対してのこれまでの状況

 ■メインリニアソルバ

Defaultは、CLPです。

INRC2　８Weeksの規模に対しては、明らかにHighs　IPMが有利です。ソフト制約が基数制約にある場合は、より有利に働くと見ています。

Instance23/24については、今のところ、Highs PDLP一択です。（近い将来　Highs　IPMがGPUを使ったコルスキー分解をサポートするようになれば、PDLPを使わない可能性はあります。）

■サブ問題(RCSPP)

Defaultは、Complete　Graph方式です。Instance22では、Graph化が困難で、部分グラフ方式となります。それ以上の規模では、部分グラフの計算時間がネックとなります。サブ問題用にHighs　MIPソルバも実装しましたが、問題外に遅いです。

CLP＋CompleteGraphをグラフを使えば、例えば上の求解時間は、十数秒で済みます。

小・中規模では、PDLPは、思いのほか遅いのです。それに、Highs　MIPを使えばさらに遅くなってしまうので、選択肢からは除外せざるを得ません。

現状の課題は、超大規模問題の想定求解時間（一週間）内に解を求められる速度のサブ問題ソルバが無いことです。この規模では、Algorithm1も使えません。ひたすらBranch＆Boundしなければならないため、余計に時間がかかってしまうことから、より高速なサブ問題ソルバの開発が必要となります。

最近の論文関係では、ラベリングアルゴリズムがあるのですが、これについても遅すぎると、見ています。

A Labeling Algorithm for the Resource Constrained Elementary Shortest Path Problem

まとめると、超大規模問題では、今までに全く知られていない高速RCSSPソルバの開発が必要になる、ということです。

instance23 Rostering w/o cardinals 時間がネック

 instance22 以上では、グラフ化が出来ないので、基数制約以外をグラフ化する方式にしました。なんとか、Rootまでは、持ってきたものの、それ以降のBranch＆Bound操作で時間がかかりすぎることが分かりました。

R_calc_timeがその計算時間で、ときに10分以上要しているのが分かります。100Rosterだと、その100倍かかり、さらにそれが数回以上収束に要しています。

このままでは、1カ月経っても目的Depthまで到達することは出来ません。想定Depthは、１０００で、１Depthに数時間かかるようでは、到底現実的な時間内には、収まりません。

大規模Lp問題に取り組む前に、まずこの問題を解決する必要があります。

Highs ipm(1.11)は、大規模問題には、パワー不足

 Highs ipmをinstance22 を W/O Cardinals Graph in rosterで走らせると、24時間経ってもROOT　LP値を得ることができません。

現状のHighs ipmで行うと、恐らくは、一カ月以上計算機を廻さないといけないでしょう。そこでPDLPに期待がかかるのですが、高精度、kkt_tolerance=1e-7にすると、IPMと時間的には大差ありません。(4060Ti)

そこで、初期は、精度を落として、1e-4からスタートし、徐々に精度を上げる方式を取ることで、高速化できないかを検討しました。1e-4ならば、高速に解が得られます。また、解の安定性のための初期スケーリング処理も必要ないようです。

下のグラフは、kkt_tolerance=1e-4での目的関数値の変化のグラフです。

精度が悪いので、目的関数値は、滑らかではなく、凹凸があります。そこで、適当に低域フィルタリングして十分傾きが≒0近くなったときに、精度を上げるようにします。これを１e-7最終精度まで繰り返して、最後に収束を判定します。ROOTまで来たら1e-7に固定しBr＆Bound処理に移行します。

Q.夜勤と当直の行制約で以下を実現するにはどうしたらよいでしょうか？

 Q.夜勤と当直の行制約で以下を実現するにはどうしたらよいでしょうか？

①    当直数を個人ごとに最大―最小パターンで最大数と最小数を決める

②    夜勤数も同様に最大―最小パターンで最大数と最小数を決める。

③    当直数と夜勤数の合計を最大―最小パターンで最大数と最小数を決めて、その範囲でシフトを割り当てる。

例

スタッフ名１は月当たり当直を１～２回、夜勤を１～０回、当直と夜勤の合計が１～２回の勤務条件とした場合。

月当たりの当直数と夜勤数のパターンとして次の４パターンになるかと思います。

当直（１～２回）	夜勤（０～１回）	計（１～２回）
２	０	２
１	０	１
１	１	２
２	０	２

 

添付したプロジェクトで試しに当直と夜勤をシフト集合で深夜としてみましたが、深夜のシフトが割り当てられてしまいます。

上表の４パターンのどれかに当てはまるシフトを実現するにはどのように制約すればよいのでしょうか？

Ans.

考え方は、正しいです。ただし、実装が間違っていました。

以下の制約で「深」は、意図した合成集合「深夜」になっていません。

合成シフト集合は、最後の方にあります。

正しくは、これを用いて、次のように制約すべきです。

スタッフプロパティシートは、

求解して、意図通りの解となることを確認しました。

＜網羅テストの仕方＞

ただし、４つのパターンのうち一つの解しか確認できなかったので、予定をソフト制約として、テストを行います。

予定をソフト化したので、適用にチェックして求解します。

全4パターンの確認が出来ました！

スケジュールナースTODO：

ラベルのシフト合成集合の明示。

コルスキー分解もGPU化へ

 Condensed Interior-Point Methods for Scalable Nonlinear Programming on GPUs

によれば、cuDSS の性能向上が著しいようです。未だ、Preview版ですが、そのうち正式版になることが期待されます。現在Highs ipm solverは、疎行列に対してコルスキー分解を使用していませんが、近い将来、GPUを用いた高速化が期待できます。

Linear Solver は、PDLPがありますが、高精度を必要な場合は、さほど速度アップを期待できません。その用途において補完できるのではないかと思います。

いずれにせよ、大規模問題については、GPU演算は必須の様相を呈しています。現在取り組んでいる大規模問題についてもGPU(4060TI16GB)のパワー不足が明らかですので、パワーアップを検討中です。

PDLPは、厳密解MIP向きではない

 KKT_toleranceを1e-7にすると、IPMよりもかなり遅くなりますし、それでいて精度も未だ十分ではありません。1e-4にして、推定値を求めるにはよいのですが、PDLPで厳密解を目指して最後まで通すには、不十分であると結論しました。

また、WarmStartもやってみましたが、全く効果がありませんでした。

そこで、Rootで、PDLPで推定⇒IPMに切り替えというのが、最も経済的なアプローチということになると思います。　残念ながらHIGHS　IPMは、未だマルチスレッド化もされていないし、コルスキー分解のGPU化もなされていないので、相当遅いのを覚悟しなければなりません。