人間がつくった勤務表と機械がつくった勤務表で品質に差はあるか？

いつか、きちんとデータを取りたいと思っていたのですが、今回データを取ることができました。
パズルを解く速度については、異論がないと思いますが、人間が十数時間かけて作った勤務表と機械が十数秒で作った勤務表では、品質にどれだけの差があるか？　というお話です。

詳しくは、こちらを見ていただきたいのですが、結論から言うと、人間の場合相当数の見落としがあるということです。（この辺は、池上先生の初期の論文でも指摘があります。）
たとえ一個でも、遅番ー早番というシフトがあったとすると、そのスタッフにとっては、苦しいシフトな筈で、不信感を生まないことを願うばかりです。

ハード制約というのは、必ず守らなければいけない制約のことですが、これが一個でも守られていないと、機械の方は、解がない、という事態になってしまいます。逆にいうと、ハード制約を全て満たした勤務表しか機械は作ることが出来ません。

一方、人間の方は、スタッフの希望最優先ということが至上命題になっていて、ついついルールを捻じ曲げてしまうということが見受けられます。「勤務表が出来た」　というのは、スタッフの希望を全部通した、になってしまっていて、元々のハード制約を捻じ曲げた結果であることに気づいていないことが多いのです。
機械の場合は、「ルール」として定めたものは、そのルール通りに配置しようとするので、ある意味融通が効かないのです。融通が効かないとは、安易に捻じ曲げることができない仕組みでもある訳です。

ちなみに、先月の勤務に制約をかけないのは、先月のルールと今月のルールが違う可能性もありますが、先月が人間が作った勤務表だと、お聞きしていたルールが守られていないことが多いためです。


脳内の制約がきちんと漏れなく守られているか？　管理する意味でも機械化をする意味があると思います。

親切な審査官

例によって、拒絶理由通知書を受け取りました。これは、一回目の拒絶理由通知と呼ばれるものです。何度受け取っても、愛を告白して、拒絶された心境になるのは変わりがありません。これから、特許査定を頂くために、手続き補正書と意見書（2ヶ月内に、同時にオンラインで出さないといけない）を出すのですが、その仕事量を考えると憂鬱な気分になります。

ところが、今回の事案は、通知書を見て頂いた弁理士さんによれば、親切な審査官ということになるのだそうです。拒絶しておいて親切とは如何なものか？今一ピンとこなかったのですが、実際に意見書を作成してみてよく分かりました。実は、今回意見書の作成は、2時間もかかっておりません。（前回特許は、数週間を要しました。）　この辺は、明細書のQualityの差によるところが大きいでしょう。弁理士さんに指導を受けて提出したものと、そうでないものの差だろうと実感した次第です。確かに、出す前は色々と指摘を受けて文言を色々追加するので大変なのですが、後々、今回の事案のように楽になることを考えれば、やはり最初から弁理士さんの指導を受けた方が得策ということでしょう。

「親切な審査官の影に弁理士さんの力量あり」　これが今日の格言です。

Lisbon Wedding

結婚式（披露宴）の席順で、悩むのは、日本だけかと思っていたら、海外でも普遍的な悩み事のようです。（ナーススケジューリング問題と同様NP困難な問題）　Finding an optimal seating chart という問題らしいです。　MIPソルバーによる解法が一般的だと思うのですが、MaxSATによる解法もあるというこで、MSE2017　Solver　DescriptionのPage25をご覧ください。ちなみにPage12は、私の今年参加ソルバーMaxRosterが載っています。

ロバストな勤務表

勤務表を自動作成して最も困難なのは、月々の予想できない仕様変更に対処することです。

つまり、月々の仕様変更という外乱に、打ち勝つ耐性が必要なのですが、これを私的には、ロバスト性を有する自動勤務表作成と呼んでおります。　自動勤務表作成は、制約によって記述されますから、ロバスト性を有する勤務表は、ロバストな制約で記述されている必要があります。これは、結構難しいことなのですが、長い経験によりこんな風に作成したらよい、という経験則が少し見えてくました。そこで、この辺のノウハウをまとめています。

オペレーションズ・リサーチ的アプローチとAI的アプローチ

Wekipediaによると
さまざまな計画に際して最も効率的になるよう決定する科学的技法である。
とありますが、学会での定義を見ると、「ORは問題の分野を選ばないという横糸的性格を持っています」　さらに、「人間社会で使われることのないORは意味がありません．みなさん，ORは実学です．」とも述べられてています。

私は、大学でORを勉強した事はありません。今にして、ORを勉強していればよかったなあ、と思いますが、その当時のMIPソルバーの性能比も数百万倍になっているわけで、その後の内点法(吉瀬先生）などのアルゴリズムの進化は、勉強していたとしても予想だにしなかったでしょう。ちなみに、大学で教わった言語は、Fortranのみで、しかもパンチカードという時代だったし、私の現在の主力言語C++は勿論存在していません。会社に入ってようやく、Cという言語でUNIXは書かれているらしい....、という時代でした。回路設計も、2000ゲートを回路図で数ヶ月というと超速レベル、その後、論理合成に基づくHDL設計という時代の後、合成も進化していきます。私のHDLシミュレータ（Veritak）も一定の貢献をしたと思いますが、アサーションのFeasibility Studyをしたところで、SATソルバーの存在を知り、当時看護師長だった妻の勤務表作成に応用することを思いつきました。（数年、妻の勤務表をモデルに改良を重ね、現在に至ります。妻は偉くなってしまい、現在は、Advanced　Usersさんを中心に助言を頂いています。）

してみると、技術の進歩というのは、私達常人には予想できないことかもしれません。
ナーススケジューリングという、NP困難な組み合わせ最適化という、一つの分野にここ数年取り組んでみて分かった事は、「最適化」　Optimizationというキーワードは、OR的手法のみならず、AI的手法においても共通しているということです。同じ事を目指しているのに、全く違う手法なのです。

一方、先端のMIPソルバーは、AI的手法の肝である学習節を持っているらしいし、SCIPにおいても制約伝播的なアプローチが取られているようです。この先どのようなイノベーションが待ち受けているかは、分かりませんが、OR(数理計画）とAI（人工知能）の融合というのが、一つのテーマではないか、と思います。

勤務表から最適化された患者サービスが始まる

希望休が多い職場は良い職場か？

この辺は、病院ない労使の決まりごと、あるいは、看護師長の裁量によるところが多いのですが、

A　全く自由に（無制限に）出せるところ
B　5日まで
C　3日まで
D　2日まで

という区分に分類されます。

看護学会に出席した妻の話では、勤務表のセクションは、立ち見が出るほど盛況なようです。Aの職場も多いようですが、皆様の悩みは尽きないようです。

ところで、

希望休が多い職場が良い職場とは実は言えないのです。


一般的に、希望休を出せば出すほど、より好ましくない勤務パターンをスタッフに強いる関係があります。


なぜならば、日本の勤務環境では、縦方向の制約、その日に必要な夜勤や、遅番、早番、残り番の数は、きっちり決まっておりソフト制約とすることは殆どありません。（増員日のソフト制約はあっても、最低限その日必要なスタッフ数をソフト制約とするところはありません。）つまり、解を得るためには、横方向の制約、看護師のシフトパターンで無理を強いる方向に作用させることで解を得ています。
謙虚なスタッフは、必要最低限の希望休みしか入れませんが、「出さなきゃ損」　みたいな感覚で出してくるスタッフも中にはいると思います。そうしたスタッフには、上の知見を理解して必要最低限を心がけて欲しい　としか言えないのでしょうか？　謙虚なスタッフと傲慢なスタッフがいたとして、勤務表は、限られた解空間で選ばないといけないので、結果として、そして全体として、より好ましくない勤務パターンを強いるとすれば、謙虚なスタッフは2重に不利益を被ることになるのではないでしょうか？　「勤務表から最適化された患者サービスが始まる」というのは、スタッフ間の公平がまず最初にあるべきと思います。

スケジュールナースは、これらの計算とシミュレーションで得られた知見から、より良いルールに向けての指針を提案しています。

RAMP講演しました。

講演資料(pptx)です。筑波大の春日講堂です。（Noteに話す内容が書いています。）


実装方法の詳細については、２０１７RAMP予稿集の方をご覧ください。（こちらは、希少で大学の図書館にもおいていない所が多いと思います。）


午前中のセッションは、機械学習で、数式のオンパレードです。先生方は、数式の世界に生きているのではないかと思いました。学会誌の編集後記で触れられています。


午後のセッションは、スケジューリング関係で、成蹊大学　池上先生、神戸大学　番原先生、筑波大学　繁野先生、法政大学　野々部先生です。（事前に東北大学の工学部図書館で、先生方の著作については、調べていました。）

大変に先生方の発表が素晴らしく、勉強になりました。

先生方に大変御世話になり恐縮でした。

大学の先生というと、卒研のときに指導頂いた位のと、会社員時代、IBM大和研究所(お客さまでした）での打ち合わせで散々叱られた苦い経験しか思い出せないので、縁のない雲の上の方々と思っていました。ところが、先生方のプレゼンが素晴らしく、昔の大学教授というのが、過去のステレオタイプだったと考えを改めました。また、お茶目な先生や、企業の研究者の方ともお話しをすることが出来、楽しい時間を過ごすが出来ました。なにより、新たな発想のヒントが得られたのが最大の収穫です。

大変ありがとうございました。
長女が講演時の法政大、野々部先生の写真を見て、「授業を受ける！」と騒いで
いましたが、本人の妄想です。（福祉大の学生です。）

プレスリリースしました。

プレスリリースしました。

MaxSATについては、ここ１-２年進歩があまり無いのですが、MaxSATcommunityにささやかながら少し貢献できたのかもしれません。そもそも、NP-困難なところの最適化に（いかにSATソルバーが強力とはいえども）booleanで何とかしようというのは、多分誰が考えても無理があるような気がするのですが、意外に行ける分野があるんですね。スケジュールナースでは、この技術を応用してさらに高い最適化を極めたいと思っております。

ユーザ事例

ユーザ様が全日本病院学会で発表されたスライドを掲載する許可を得ました。（なお、スタッフ名は、実名ではありません。）経営的な観点からも、示唆に富んだ内容で素晴らしいです。

新しいパラダイムに挑戦して、効率化とスタッフのQOL向上を成し遂げるられています。スケジュールナースを全くサポートなしに機能を使いこなしておられる方が、私の知る限り数人おられますが、この方もそのうちのひとりです。

この方も指摘しておられますが、ナーススケジューリングの場合、制約が月毎に変わります。このことがハードルを一段も二段も高くしておりサポートが必要な理由になっています。　

アルゴリズム研究者とフィールドエンジニアそして実際にお使いになられるお客様、よりよいシステムにするためには、各々どうしたらよいか？　その事を日々考えている今日この頃です。

RAMPシンポジウム

プログラムのタイトルが決定したようです。

RAMPシンポジウムは、日本オペレーションズ・リサーチ学会の数理計画研究部会 (
RAMP: Research Association of Mathematical Programming) によって年一度開催
される、最適化、数理計画に関するシンポジウムです。 

著名な先生方の講演があります。機械学習や最適化、スケジューリング最適化等、現在の日本で最も先端のお話しが聞けます。

私は、実務的な観点でナーススケジューリングの現場での問題、そして、MaxSAT　Competition結果とその応用においての得意・不得意等、予稿に入れてないものを中心にお話ししたいと思います。是非いらしてください。

商標出願

というものを初めてやってみました。スケジュールナースの新しく実装した機能を、説明をしようと思ったのですが、名前がないと説明しずらいことに気づいて名前をつけてみることにしました。スマート・AI・インテリ..等の組み合わせ語になるのですが、殆ど、先願があって没になりました。
（弁理士さんによれば、特許とは違い、実際にその商標を使用することが条件だそうです。一杯商標を取っている会社？があるようですが、本当に使っているのか疑問です。
ー＞後で分かったのですが、参考記事　の通りのようです。
）
自分でも調査したのですが、やはり、弁理士さんにやってもらったほうが確実です。実際、自分では見つけられない指摘を頂きました。また単に英語を日本語にすることによって避けても観念が同じでNGだそうです。（有名な例は、午後の紅茶）　ということで、この点でも弁理士さんに相談した方がよいでしょう。

RAMP講演

10月12日筑波大学にてA SAT approach to Nurse Scheduling Problemというテーマで、講演します。予稿を今執筆中ですが、正直面白くないと思います。
その頃には、MaxSAT　Competition２０１７の結果も出ているだろうし、参加したソルバー（maxroster)と他のＳｔａｔｅＯｆＡｒｔソルバーも結果が出ていると思います。もし可能ならば、そういったお話しもスライドでは行いたいと思います。楽しみにしていてください。

特許出願手続き

出願、出願審査請求書、早期審査に関する事情説明書をオンラインで提出しました。

出願については、簡単願書作成で初稿は書いたのですが、弁理士さんが手直しする関係でWORDに移行しました。ＷＯＲＤだと変更履歴管理が完全です。

その後、数回やりとりして役一ヶ月で完成しました。
最後にDOCUMENTの検査を行って、コメントやら変更履歴をDeleteします。その後、フィルタ付きHTML化を行って、出願ソフトへD&Dを行い、チェックします。OKなら、オンラインタブで送信して終了です。送信時に、出願ｘｘｘというNOが取得されるので、そのNoを出願審査請求その他の文書作成で使用しその日のうちにこれも送信しました。

明細書は、素人（その分野では玄人ですが、特許については素人です。）でも何とか書けますが、クレームについては、素人では絶対無理だと思います。その分野に精通した弁理士さんに見てもらいましょう。（仙台でソフトウェア関係でしたら紹介できます。）

あせったのは、前は、オンラインで出願するのに、前は住民基本カードだったのが、マイナンバーになっていて、慌てて登録したのですが、どんなに早くても一ヶ月はかかるようで、お役所に文句を言ったら少しだけ早くなり間に合いました。

特許料4年目以降の支払いメモ

2025年の君へ

１）電子現金納付制度を利用して納付書NOを取得してそのままONLINEで銀行から振りこみする
２）4年目以降の減免申請をWORDで作成　特許庁に郵送する
３）納付書をオンラインで送る。フォーマットは、雛形（特許料納付書（年金）がHTMLであるのでそれを手修正する。送信ファイルにD&Dするとチェックが始まる。しかし、特許権者　を追加、出願人。。を削除しないと入力チェックでエラーになった。エラーを取ったらオンラインのタグがEnableされるのでオンラインで送信。ひとつづつ送信される。受領を確認して終了。

２０１８-9/18から4年目
2019 -5
2020 -6
2021 -7
2022 -8
2023 -9
2024 -10
2025 -11      この年から毎年支払う。とりあえず、10年まで2017－4/１-2027 3・31　より、
　　　　　　　　2027年までは、８月中に払う必要あり。毎年１）３）を行う。

MSE2017 Testing

主催者が用意してくれたベンチマークがWeightedとUnweightedで各50個あり、SolverをUploadして、StarExeClusterにジョブを投げます。Permissionの問題がありましたが、主催者が対処してくれました。(ということは、他に未だ誰もテストしていない??? )

1)Archiveの仕方
まず躓いたのは、UploadでWrapperFolderを含めてはいけないことでした。普通にzipでやってしまうと含まれてしまうので、CurrentDirに入って、

tar cvf aaa.tar ./*

とやってtar FILEをつくり"upload solver"を実行します。

それから、TESTフォルダに入って"create_job"でソルバと動かしたいベンチマークのペアを指定します

２）staticに注意

基本的に実行ファイルは、-static でビルドされている必要があります。いきなり即終了したので変だなあと思ってログを見ると、*.soが見つからないというエラーで実行されていませんでした。StarExecは、古いLinuxらしいです。failureとして報告されないので、要注意です。ログは見るようにしましょう。

３）sigterm

InComplete部門は、SigTermが来たらSolutionをプリントすることになっていますが、どうも来ない疑いがあります。そこで、本来のTIMEOUT直前5秒前に発生させて実行しました。(90sec/300sec各トラック用にScriptを用意）

timout  85     ./EXE $1
timeout 295   ./EXE $1

これで一応いけることを確認しました。

その後、事務局より、現在、SIGTERMの後に数秒してSIGKILLするようにStarExecの管理者に依頼中とのことで、来週には改善されるだろうとのことです。

SIGTERMのDebug用として、runsolverを紹介されました。これ上で走らせれば、SIGTERMとSIGKILLを自由なタイミングで操作可能とのことでしたが、local machineで、fileに出力させながらやってみると、強制終了が、いくつかでていました。特にTIMEOUTのところで出ている訳ではないので不思議です。とりあえず、上記方策を、事務局に提案しておきました。

=>
その後、予想通り、SIGTERMとSIGKILLのDelayは、User責任になったようです。最終的には、以下のスクリプトで提出しました。displayの処理時間は、User責任なので、最後のflush(stdout)するのを忘れないようにしましょう。

#!/bin/sh
delay=5
wl=`expr $STAREXEC_WALLCLOCK_LIMIT - $delay`
#echo $STAREXEC_WALLCLOCK_LIMIT $wl
timeout $wl ./maxroster $1

最大インスタンス（d4.wcnfで、約1400万変数)でも殆ど時間がかかっていなかったので5秒も取る必要はなかったのかもしれません。

４）テストの確認
主催者が50インスタンスづつ用意してくれているので、それでcreate_jobで確認します。
なぜか、他の人のソルバーもテストすることも可能でした。

create_jobが終ると、job_informationで、CSVファイルをダウンロードします。
こんな感じです。

pair id	benchmark	benchmark id	solver	solver id	configuration	configuration id	status	cpu time	wallclock time	memory usage	result	optimum_solution	hard_clauses	optimum	checker_solution	checker	given_solution
290700075	Weighted/1401.wcsp.dir.wcnf	4414170	maxroster	11897	default.sh	219868	complete	85	85.01	250044	--	459106	satisfied	FALSE	459111	ok	459111
290700076	Weighted/1401.wcsp.log.wcnf	4414171	maxroster	11897	default.sh	219868	complete	84.99	85.01	256424	--	-1	satisfied	FALSE	467103	ok	467103
290700077	Weighted/1403.wcsp.dir.wcnf	4414172	maxroster	11897	default.sh	219868	complete	85.01	85.01	248172	--	459246	satisfied	FALSE	459274	ok	459274

chekerの計算した値<=自分のソルバーが計算した値になっていることを確認します。

５）所感
締め切りの2日前になってもカテゴリーやらスクリプトが変わりました。オーガナイザが変わったので致し方ない面があるかと思います。来年からは、今年の経験を元に改善されることでしょう。

=>
締め切り日が変更され2週間遅れます。

結果は、SAT２０１７で発表されるそうです。

MaxSAT Competition 2017 のIncompleteのルール

事務局に問い合わせたので、メモしておきます。

60秒と300秒は、別なトラックになります。各々Unweight/Weightのカテゴリーがあるので，好きな方（もしくは両方）に参加してもよい。

Webには、

 Incomplete score:
    ∑i ∈ instances (cost of solution for i found by solver)
                      / (cost of best solution for i found by any solver)

現実には、こういうことらしい。

Σ　i ∈ instances　A　Score

A　Scoreは、best_solutionのとき１、それ以外は０、従い、virtual best solverのスコアは、インスタンス数になる。（スコアが高いほど1位を取ったインスタンス数が多い）　

ベンチマークテスト更新

池上先生が公開されているベンチマークをプロジェクト変換して、アップしていたのですが、
池上先生から、KnownBestValueと違うよ、と指摘されました。見直した結果、変換に酷いバグがあることが判明したので、バグ修正しました。最新版のソルバでは、求解アルゴリズムを一つ追加したのでその結果も合わせて載せております。

MaxSAT Competition 2017にエントリしました。

今年から、大分ルールが変わったようです。

まずオーガナイザが、現役のトップアスリートになったようです。MachineがStarExeClusterというSAT　Competitionでも共用するClusteringMachineになりました。１Instanceあたりのメモリが２４GB、MainTrackの制限時間が１時間という仕様に代わりました。
　MainTrackでは、StateOfArtのソルバがひしめきます。こちらはAcademicな観点からMaxSATの主戦場でしょう。対して、NSP(NurseSchedulingProblem)は、実質的な解をReasonableな時間内に得ることが主眼であって必ずしも厳密解にはこだわりません。そのため、InCompleteTrackで出場することにしました。こちらは、６０secまたは、300sec内となっており、実際の現場での仕様状態に近いものです。
今回は、アナウンスから締め切り（6/15)が極端に短いので、逆に有利かもしれません。まだ、11組しかおりませんでしたし。

ともあれ、NSPのCompetitionでもそうでしたが、ソルバを作ってチューニングをするのは、子どものころのプラモデルを作る楽しみに似て、心躍るものがあります。
　Clustering上でテストもできるようなので、そのうちテストしてみたいと思います。

独占ライセンス契約を締結しました。

締結先は、マルマンコンピュータサービス株式会社です。

ソルバ（求解エンジン）の独占ライセンスですので、スケジュールナースには何等影響がなく、これまでどおり販売・サポートしていきます。