スケジュールナースのブログ

2024年7月26日金曜日

INRC2 8Weeks LB　改善構想

改善方法を構想しました。

一つには、BranchingTreeのパラレル化です。マルチスレッドで、残っているBranchingTreeを潰していきます。ネックは、グラフを解く速度ではなくリニアソルバCLPの速度であることが分かっているので、CLPのマルチスレッド数がその上限の速度向上となります。しかしながら、この方法でも十分ではありません。

そこで、LB改善専門の専用スレッドを立ち上げます。このスレッドは、LB(Lower Bound)が求まったあとに、通常のBranching　Tree　Search（左側）とは独立、かつ並列にLBだけを改善します。

LB改善とは何か？というと、リニアソルバで求めたBranching　Tree　Rootのフラクショナルな値を整数化していくことです。それでは、Branch＆Boundと何が違うか？というと問題を分割しません。Rootのまま行います。なので、そこでフラクショナルを整数に出来たとき、何某かLB改善に寄与するはずです。その問題の目的関数値の最小公約数で決まる値以下にUB-LBギャップまで改善出来た場合、最適値証明が完了します。INRC2の場合は、最小公約数は、５です。（重みが１０，１５，２０，３０）です。必ずしも全てのFractionalを整数化する必要はありません。UB-LBギャップー５>=0となるまで改善出来れば十分です。別な言い方をするなら、全てのFractionalを整数化出来た時、UBが未知だとしてもリニアソルバの値が即最適値UBとなります。

INRC4Weeksのように通常は、左側ループのみで厳密解が求まります。しかし、長時間廻しても求まらない、若しくは求まらない可能性を考えて右側ループも最初から廻します。現在の状況からするとINRC8Weeksの場合は、1時間も廻すともうこれは尋常ではない＝BranchingTree爆発ということが分かるので、その時点で右側に全力投入したほうがよいかもしれません。

これは、INRC8WEEKSに対して8時間以内に厳密解が求めるためのアイデアであり、やむにやまれず、手段を選んでられない状況から考えました。もう意地になっているいうか、これを解くことが自分の使命のように思い込んでしまっている自分が怖いです。

ところで、整数計画創始者ゴモリーの考案した方法は、ゴモリーカットと呼ばれています。

Vol.50_10_719.pdf (orsj.org)

The history of state-of-the-art MIP solvers is fascinating. There are very few p... | Hacker News (ycombinator.com)

CPLEX→CLP/Gruribi→ZIB/Highs→COPT

という最近のCOPTの攻勢をみるにつけ、アカデミックなバックグラウンドは、全て繋がっている、のが面白い、というかそれだけ難しい分野ということが言えると思います。最先端のMIPソルバを開発できる人は、非常に限られており、会社から会社へ移動することによって成長と遂げてきたという歴史があります。COPTの中の人達も、スタンフォード出身だったのですね。

とりあえず、この方法を菅原カットと呼ぼうと思います。平面削除は、アナログをデジタル化する方法です。一方、菅原カットは、デジタルからアナログを改善する方法です。実装してみて、どんなものなのか、今後数週に渡り、実装・評価していきます。

2024年7月25日木曜日

INRC2　8WEEKS　LBの改善が必要

２００時間廻しても解が得られないのが大半であることが分かりました。正確には、厳密解証明が出来ていません。約１０日計算機を廻しても解が得られないというのは、何か方法論からして間違っているような気がします。

どういう問題かというと、BranchingTreeの爆発という現象が生じて、調べるのが困難になるということです。Branching Treeを全て調べて、現在のUBを下回る解が存在しない、ということを言いたいのですが、調べれば調べる程、調べるべきNodeが増えてくる現象です。つまり、恐らくこの値は最適値であろうが、これより良い解が存在しない、という証明が出来ないのです。

そんなこと、どうだっていいじゃん？ほぼ最適値が分かっているんでしょ？と言われそうですが、アカデミックの世界で重要なのは、厳密解です。これが言えるかどうかで、その価値に雲泥の差が生じます。厳密解が分かれば、その後、高速なヒュリスティクスを開発することも有利になります。しかし、それが分からないと、現在の解がどれだけ最適値に近いのかが分からないということになります。量子アニーリングがどれだけ早くかつ精度よく問題を解けるのかは？最適値が分かっている最も困難な問題分野で、比較評価されるべきでしょう。そういった評価をする上においても重要です。量子アニーリング自体は、厳密解を求めるものではありません。厳密解を得るのは、依然としてクラシカルな方法によります。

NP困難な世界に挑むとは、そういうことだと思います。

この手の問題に対して一般的なMIPの対処方法は次の３つがあります。

■Strong Branch

■Reduced Cost Fixing

■Cut　Generator

です。代表的な組み合わせ最適化問題、例えば、VRP(Vehicle Routing Problem)問題では、Cut　Generatorが有効であることが報告されていますが、NSPに関しては殆どありません。

どのようにするか、するべきか考え中です。

2024年7月24日水曜日

サブスク契約

Q.スケジュールナースシステムの利用について、サブスク契約するにあたりの、見積り

書とメンテナンスに係る経費の概算を教えてください。

Ans.

サブスクは、マイクロソフトストアによる販売です。菅原システムズは、ソフトの開発元ではありますがサブスクの販売は行っておりません。

従いまして、契約書はありません。

もしかして、勤務表作成サービスの方をご所望でしたら、以下のような内容になります。

https://www.nurse-scheduling-software.com/japanese/publications/project_creation_service.pdf

お勧めしているのは、1年サポートの方です。実績的に見ますと、３カ月＋サブスク版では、ITに明るい方でないと期間的に難しいかな？という感じです。慣れの部分大半ですが、厳しい方が散見されます。

１年版でしたら、買い切りであり、この期間内に学習して頂ければあとはご自分達でメンテナンス出来るので費用負担も発生しない、という算段です。

勿論、独力で可能であれば、買い切り版のみの販売もお受けします。

以上、ご案内させていただきました。

2024年7月23日火曜日

入稿データ作成

印刷媒体に広告を出すのは初めてなので、以下の通りご教示頂きました。

*****

ご質問いただきました入稿データの件ですが、

添付のpptの黒枠内にモノクロで作成の上、PDF保存お願いします。

その後、以下URLにてグレースケール変換※をお願いします

（※グレースケール変換しないと印刷データとしてNGのため）

https://avepdf.com/ja/convert-pdf-to-grayscale

また、特に最小フォントなどの指定はございませんが、

文字のアウトライン化をお願いします

※アウトライン化の方法は以下URL参照お願いします

https://ppdtp.com/powerpoint/font-outline/

また、貴社HPのURLが記載されておりますが

QRコードは不要でしょうか？

もしご希望でしたら、以下URLにてQRコード作成可能ですので

作成後、広告データ上に配置の上、最後グレースケール変換いただければと存じま

す。

https://barcode-place.azurewebsites.net/Barcode/qr

*****

ということで、本来なら、版下作成にイラストレーターが必要ところ、

１）所定のPPTテンプレート上で作成

２）アウトライン化

３）PDF化

４）PDFをグレースケール化

で、済みました。サポートありがとうございました。

2024年7月19日金曜日

Nursing　BUSINESS１０月号に広告を掲載予定

勤務表作成の特集があるようで、その縁で広告を掲載することにしました。

現在Google広告を使用していますが、「看護師」「勤務表」「自動」での広告単価は、時に、＠３５０を超えてます。数年前に比べ、数倍～１０倍に高騰しています。一方、スケジュールナースのサブスクで手元に入ってくるのは、＠３００足らずです。(マイクロソフトは＠１５％ですが、そのほかにUSのTAXが取られます。)　いつの間にか、とんでもないことになっていました。つまり、製品の原価以上に広告費が高い、という異常な状態にあります。

それだけ価値のあるような競合製品群になっている、とも思えないのですが、民生分野からすると、医療分野は、美味しい分野なのかもしれません。そもそも、アプリの志向が違うので競合とも言えないのですが、傍から見ると同じに見えるのでしょう。

スケジュールナースは、簡単ではないしAIも使っていません。

アプリの設定を使うというよりは、アプリにプログラムする、もう少し正確な言い方をすると、制約プログラミングするためのプラットフォームです。ユーザは、アプリの下にあるのではなく、ユーザ自身が制約プログラミングするところが決定的に違います。

ただし、いわゆるプログラミングではありません。プログラムは、問題を解くやりかた、アルゴリズムに沿ってコーデイングしますが、制約プログラミングは、アルゴリズムを解くことではありません。制約プログラミングは、制約を列挙することであって、問題を解くやり方をコンピュータに指示する必要はありません。制約を列挙しさえすれば、後は、制約で決まる解空間上での最適解を求めるのはソルバの仕事です。

とりあえず、どんなものかな～位の気持ちで試してみることにしました。

2024年7月18日木曜日

HighsのHiGHS Newsletter 24.1

ワークショップがあったようで、結構な参加者がいたようです。資金調達も上手く行っているようで、スポンサーも付いているようです。

トピックは、内点法ソルバのプロトタイプを８月末までにリリースするとのことです。また、開発の議論の場として、Discordを始めるようです。Metisによるパーティションニングを施すとのことなので、恐らくは、マルチスレッド化したものになるでしょう。

なので、それなりの性能アップが期待できます。この性能を見た後に、必要ならCOPTに切り替える作戦でもよいかな？と思いました。とりあえず、厳密解を全て明らかにするという壮大な仕事が終わってから、普及活動に戻りたいと思います。

2024年7月17日水曜日

夜勤ナースと夜勤支援二つのグループに属する夜勤者数の変更の仕方について

次のような大変丁寧なご質問を頂きました。この質問の優れた点は、問題箇所の説明であることは、勿論ですが、、再質問の余地がなく、必要にして十分な情報が盛り込まれています。しかも、ご自分でトライして、このようにしたけれどもダメだったと、記述されていることです。

このように記述して頂くと、どこで躓いているのかが分かるので、大変ありがたいです。

「夜勤」というシフトを今まで、各Grから一人づつ、計2名確保していたけれども、新しく、どちらのGrにも属せる人が居た場合は、上のように制約したい、とのことですね。これに対する私の一次回答は次です。

夜勤というシフトを二つに分けるのよいかと思います。

夜勤＝夜勤ナース業務　または　夜勤支援業務

とします。

次の3つの制約で、所望の動きになると思います。

１）1<=夜勤ナース業務<=2

２）夜勤支援業務<=1

３）2<=夜勤<=2

３）番目の制約は、夜勤する人は、変わらず2人、という制約です。これは異論ないと思います。１）番目の制約は、ナース夜勤でみると、上の二つのケースでみて、2人のナースの方が夜勤する場合と、1人のナースと1人の支援業務の方の場合があります。どちらのケースでも、最低ナースは一人確保されている必要があります。最大で2名は異論ないと思います。２）番目の制約は、二つのケースで見ると、0名もしくは１名となります。

一つのシフトは、同じ人には二つ割り当てられることはなく、常に一つという性質を利用して制約します。スタッフプロパティ上の集合は、どちらの集合にも属する場合が出てくるので、仕事を分けるには、シフトを分けることが必須になります。（今後、さらに夜勤の種類が増える場合には、タスクを使うことで、シフトとタスクの分離が出来、メンテナンス性がよいものとなりますが、今回の場合は、シフト分割でよいでしょう。）

分かりづらければ、現在のプロジェクトファイルを送って頂ければ、それに上記を追加変更いたします。

ということで、具体的にプロジェクトを変更していきます。

夜勤シフトのチェックを外します。

すると、次のようになります。