2019年8月19日月曜日

one drive 版32ビット版

一日がかりでコンパイルしました。開発は、1年以上64ビット環境でしか行っていませんでしたが、
意を決して、ソースから全部のコンパイルを行いました。使っているライブラリの量が尋常ではないです。多分エディタのソースまで含めたら50万行はあると思います。

C#系のDLLは、一つあれば足りるので便利です。C++Native系は、どうしても32ビットと64ビットで分けざるを得ないです。

とりあえず、HomeMachineは32ビットなので、これからはHome MachineでPythonコードを書きます。

2019年8月13日火曜日

2019年8月11日日曜日

ClosedXML DLL エラー

ExcelのImport・Exportに使用しているClosedXMLで、クラッシュします。(Excel書き込み読み込み時)
原因を見てみるとDependencyDLLの一つでFASTMEMBERxxが見つからないというエラーです。
このClosedXMLは、結構な量のDLLが必要で、それらを全て最新にしてみても状況は変わりません。

原因は、特定のDLL Versionが必要なようでした。明示的に読み込ませる必要があります。schedule_nurse3.exe.config というファイルを添付することで、明示読み込みが出来るようですので、今後添付するようにします。Onedrive上の更新は、Excel読み込みライブラリの更新を含めて8月13日を予定しています。

2019年8月10日土曜日

凸最適化 first-orderに注目

OR学会誌 6月号で、一次法の特集が組まれています。タイムリーな特集です。一次法の逆襲という的を得たタイトルです。

線形目的関数の世界では、Simplexと内点法が幅を利かせていますが、大規模な制約の場合、例えば、NSPで言うと6ヶ月とか1年とかになってくると、Simplexでは苦しくなってきます。そこで内点法の出番ですが、商用ソルバーはともかく手に入る実装では、やはり厳しいものがあります。そこで最近、注目しているのが、first-orderです。

http://www.orsj.or.jp/archive2/or64-6/or64_6_314.pdf
http://www.orsj.or.jp/archive2/or64-6/or64_6_316.pdf
http://www.orsj.or.jp/archive2/or64-6/or64_6_335.pdf

画像解析、機械学習で注目されていますが、NSPでは、未だ論文が発表されていません。

現在、SC3 algorithm4は、未完成です。汎用化まであと一歩なのですが、殆どの実用的な問題ではalrogithm1に負けます。優勢なのは、ほぼ学会ベンチマークのみです。しかし、実務問題の中でも大規模かつ複雑な最適化問題でalgorithm4は,より厳密解に近い解を得られる可能性があると見ています。実用的な意味で、algorithm1が最適なことは変わりありません。しかし、エラー数が多種、多様、多数ある場合、つまり探索時間が一桁・二桁余計にかかるような問題では、数理的なアプローチが有利になってくる、ということだと理解しています。

数理的なアプローチとしては、線形ソルバーを使うことになる訳ですが、今までは、Simplex・内点法のアプローチしか考えられなかったのですが、first orderソルバーも可能性が出てきた、ということです。

2019年8月9日金曜日

週あたりの勤務回数 の実装

これを制約開始日ベースで記述しようとすると


制約表示日制約開始日
オフセット0123456789101112131415
1234560123456012
端数第一週第二週




最後の週が2月28日を除いて端数になってしまいます。
そこで、曜日ベースで記述することにします。


制約表示日制約開始日
オフセット0123456789101112131415
第一週      


その場合、毎月、曜日集合をGUIで指定します。制約開始日または、それ以前の月曜日を基点として、以降未来永劫月曜日基準で制約することにします。

ユーザは、毎月の月曜日を指定する必要があります。年間カレンダで年単位一回でGUI指定することは出来ます。しかし、その場合でも最後の週に対して目標値の修正は、必要です。やはり面倒なので、Pythonで記述することにします。

<プロジェクト名_property.pyの記述を利用する>

プロジェクト名_property.pyを覗いてみると、
次のように定義されています。

今月は、Dayオフセット6-36まであることが分かります。(上図どおり)
これで、月は、Dayオフセット3,10...
であることが分かります。最後のところだけ、31,32,33,34,35,36の6日間になり端数処理が必要となります。

#daycollection
今月=[6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36]
日=[2,9,16,23,30]
月=[3,10,17,24,31]
火=[4,11,18,25,32]
水=[5,12,19,26,33]
木=[6,13,20,27,34]
金=[0,7,14,21,28,35]
土=[1,8,15,22,29,36]
全日=[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36]
祝=[16]

月曜日のDayオフセットテーブルを読み込んで各週の制約を書けばよい事になります。

<スタッフプロパティに定義されたスタッフを見る>
週当たりの勤務回数は、特定の契約スタッフのみについて行われます。この情報は、スタッフプロパティで記述されていて、以下の通りプロジェクト名_property.pyで記述されています。

#digited group
公休数={1:13,2:13,3:13,4:13,5:13,6:13,7:13,8:13,9:13,10:15,11:13,12:13,13:13,14:13,15:13,16:13,17:13,18:13,19:13,20:13,21:13,22:17,23:13,24:13,25:13}
週あたりの勤務回数={22:3}

公休数と、週あたりの勤務回数がMapで記述されています。PersonOffset:回数の形式に
なっています。PersonOffsetは、0ベースでのスタッフナンバーです。Person1の公休数は13、Person22の週あたりの勤務回数は、3という風に定義されています。定義されていないスタッフについては、該当Mapでは記述されません。例えば、Person0の公休数は定義されていません。定義されていないのは、制約対象外となります。

週あたりの勤務回数対象者は、上記Mapから得ることが出来ます。

最後は、端数処理です。週の日数が7であるときは、通常処理、それ以外のときは、端数処理で、
目標値をリニア補間で修正します。つまらないところで、ハードエラーは起こしたくないので、エラー許容量は、多めに設定(4)します。この値は、GUIでは修正されません。


<確認方法ー単独で試験する>
各週の値を、GUIでは表示することは出来ません。また、その他の制約により、上記制約がエラー0で動く保証がないので、それ以外の全てのソフト制約と予定を外して、必ず上記制約がエラー0で出来る環境を整えてやります。


以下のログを得ました。

コンパイルの準備中ソルバを呼び出し中です。
 python propertyファイル生成を開始します。
 python propertyファイル生成が終了しました。

A23の週当たりの勤務回数は3回に制約
月曜日 3
月曜日 10
月曜日 17
月曜日 24
月曜日 31
2に目標値を設定しました。


予定通り、エラーは、出ていません。person22(A23)の週当たりの勤務日数をGUI上の解で確認します。
確認後、消した予定を元通りにして(取り消し動作)、ファイル保存して終了です。

これで、カレンダ参照設定は必要なく、将来の変更(週あたりの勤務日数、対象者)に対しても強い記述が出来ました。Excel上のスタッフプロパティだけで指定が可能となります。



2019年8月8日木曜日

Python EditorをScintillaNETに変更

AvalonEditからScintillaNETに変更しました。

https://github.com/jacobslusser/ScintillaNET

Pythonでは、インデントそのものが文法になっており、スペースとタブとの混在等が、文法エラーとなります。その手のエラーで悩まされる時間を少なくするにはWhiteSpaceをVisibleにしてくるエディタが必要です。AvalonEditでその設定を探したのですが、見つけられませんでした。

そこで、NotePad++で使っているライブラリScintillaNETを試したみたところ、すんなり実装できたので、エディタを変更することにしました。

下のようにちょっと見栄えが悪くなりますが、タブが→で明示されており、これでインデント絡みのエラーは、解消できると思います。






2019年8月7日水曜日

python editor にAvalonEdit

EditorLibraryとして有名なAvalonEditをPython Editorとして採用しました。
PythonのSyntaxHighlightingが格好よいので、気に入っています。

Pythonを書いていると、頻繁にSyntaxErrorが起こります。Tab絡みの記述エラーが多いです。
エラー箇所の特定には、LineNumberが不可欠です。

Pythonでの制約記述方法については、独立したチュートリアルを準備中です。

例えば、下は、

1)Excelで、スタッフ予定(ソフト制約含む)+スタッフプロパティ(スタッフ毎の公休数を含む)を記述
(月毎に異なる部分)
2)上記Excelシートをインポート
3)求解
 A)python property fileを作成
 B)python interpreter起動
 C)pythonで、ソフトハード制約生成
4)求解エンジンへ

という流れでの、3)Cの部分です。
例えば、右下ペインの ”A1の公休数は、13回に制約”は、左下Pythonソースで生成されたものです。
 
スタッフ毎に契約が、違うのでグループ集合で記述するよりもメンテが楽できそうです。


2019年8月6日火曜日

ソフトエラー・ハードエラーの背景色追加

下のように、ソフトエラーは黄色、ハードエラー(列ソフト化化オプション使用時のソフトエラー)は、赤で表示するようにしました。基本的にハードエラーは、解なしになってしまうので表示できません。表示できるのは、列ソフト化したところのみです。

求解を途中で終了したもの


人がマニュアル作成した勤務表をインポートしたもの。

2019年8月4日日曜日

Python インタープリタの軽量化

インストール後350MB程度あるので、何とかする必要がありました。
https://qiita.com/mm_sys/items/1fd3a50a930dac3db299

こちらの記事の通りにしたら、unicode**を除いて動作しました。
今後は、Python3.68ベースにpython インタープリタで制約を記述していきます。

2019年8月3日土曜日

勤務表の設計は2012年8月を使う

2012年8月は、31日あり、土日回数が8回です。月単位で勤務表を作成している職場では、一番つらい月になります。ですから、この月で検証しておくことは、勤務表設計で意味があります。

前回行った正循環は、2019年11月で、祝があり、しかも30日、公休が9、計10の休みがあり、楽な月です。そこで、厳しい月、2012年8月でも可能かどうかを検証します。
この月は、公休8で、祝もありません。


求解し、もっとも厳しい月でも完全正循環が実現可能なことが分かりました。

ところで、目的関数値が2000になっています。
重み1000に対応するのは、行制約レベル6です。
そこで、行制約レベル6の記述を確認します。


夜勤回数8回が満足できていない箇所が1000x2=2000ですから、2箇所あることが分かります。
一番上の図の左ペインを見ると、確かに、夜勤回数が9回(=5+4)になっているスタッフが2人いることが分かります。
重み1000の脇の許容エラーは、1に設定されています。これは、制約8回Maxのところ、1だけ緩和して9回までは許すことを意味しています。つまり9回Maxでハード制約されています。
もし、9回のスタッフが一人いるとエラーカウント1になります。8回のスタッフは、エラーカウント0です。
このように許容エラーは、ソフト制約が際限なく緩和されることを防止する働きがあります。
(ちなみに、許容エラー0にするとハード制約8回Maxという意味になります。)

ところで、9回のスタッフが2人出ることが分かりましたが、これを数学的に確かめてみましょう。

夜勤可能スタッフは、23人、31日稼動、深夜3人、準夜勤3人ですから、


夜勤可能数スタッフ23人、夜勤回数8回で、可能か?
 スタッフ数日数必要コマ数
準夜勤33193
深夜勤33193
186
夜勤回数夜勤可能スタッフ数可能コマ数
 823184

これより、必要コマ数に対して2コマ足りないことが分かります。23人8回で廻すことは不可能で、
9回の人が2人、もしくは、10回の人が1人必要なことが分かります。ところで、10回は、上記制約で
禁止されているので、必ず9回の人が2人発生する、ということになります。

<許容エラーの役割>
もし許容エラーという制約がないものとすると、9回2人、10回1人どちらもCost=2000で、Costに差がありません。ソルバは、の仕事は、目的関数値の最小化だけであり、どちらに転ぶかは制御できません。つまり10回の人が1人発生する可能性があることになります。

以上は、希望年休を全く取っていない検討ですが、実場面では、さらに厳しくなります。希望休みは、予め決められた予定を入れてシミュレーションをお勧めします。

本プロジェクトは、OneDriveプロジェクトサンプル/完全正循環 フォルダにあります。
公式リリース時にも、同フォルダにプロジェクトはあります。

2019年8月1日木曜日

完全 正循環の実現

検討依頼があり、スケジュールナースⅢで、検討しました。


総スタッフ数24人看護師長含む    
夜勤可能スタッフ23人     
A/Bチーム  
深夜勤務3 A/Bチームより各1人以上・若手は1人まで
準夜勤務3A/Bチームより各1人以上・若手は1人まで
平日日勤11人以上     
休日日勤6人     
休日日勤Aチーム3     
休日日勤Bチーム3     
休日日勤ベテラン1人以上    
公休9回祝休1回      
検討月2019年11月     
深夜の前公休または祝休のみ 
準準禁止  
深深禁止  
深準禁止  
準深禁止  
5日日勤できれば避ける    
土日休み前後に夜勤のない連続休みができれば1回以上 

完全正循環になっています。希望休みの入力は、0ですが、完全正循環を実現した勤務表は
初めて見ました。
土日休みは、要求になかったのですが、看護協会の指針に沿って入れてみました。
これで、看護協会の指針に完全にマッチした勤務表の完成です! 全てが準公深パターンになっていることに注目してください。この解は今まで知られていなかった新解だと思います。スケジュールナースⅢのパワーは、もうすぐそこまで来ています。



2019年7月30日火曜日

schedunule nurseⅢ one drive版

インストーラは、準備できていません。当面64Bit版のみです。
私のテスト環境をそのままOneDriveに上げています。日々、更新しているので、バージョン管理はありません。(正式リリース版時と互換がない場合があります)
とりあえず、マニュアル(途中)を用意しました。

one driveのフォルダをコピーしてください。
GUI EXE、schedule_nurse3.exeは、sc3_test/sc3/sim_engine32にあります。
ショートカットを作成して起動してください。



2019年7月26日金曜日

SAT RACE 2019

今年は、SAT Competitionはなくて、SAT RACEでした。SAT19 Conferenceで結果が発表されております。最新のProceedingsが8月までは、フリーアクセスできます。Armin Biereさんと、Fahiem Bacchusさんの論文に注目しています。
来年は、Armin BiereさんのCaDiCalがトップを取りそうな気配です。

2019年7月25日木曜日

メインソルバ マルチスレッドの評価

簡単に評価してみました。
結論的には、効果のある場合もあるし、ない場合もある、という微妙な結果になりました。

これは、SATとかメタヒューリスティクスの世界では、よくある話です。こちらでもSatisfiable problems are well-known to have unstable solving times. と述べられている通り、解が見つかる・見つからない というのは、確率的なものです。RandomizerのSeed値を変えただけで、10倍速度が違うということは、往々にしてあります。ですので、ソルバーの真面目な評価は、カクタスプロットという多数のインスタンスを用いて、統計的に評価するのが一般的です。

下が、求解後の画面です。各重みに対するエラー数の表示を追加実装しました。



下は、中規模のインスタンス結果で、NRCⅡn030w4-16291です。このインスタンスの厳密解は、1660-1670内に存在することが分かっています。(数理的ソルバ(アルゴリズム4)で数時間RUNした結果) 

確かに、CPU数(スレッド数)が大きくなると求解時間は、減少傾向が確認できますが、目的関数値は、改善傾向にあるとは言えません。

Xeon E5-2620 2GHz 28GBRAM(6コア12スレッド)

さらに、非常に重いハード制約のインスタンスの結果が次です。
グラフにするまでもなく、マルチスレッドでは、非常にばらつき、なおかつ改善どころか,改悪傾向
にあります。


CPU数求解時間(sec)備考
1189求解時間は安定(SC2では1688sec)
2Timeout(2000sec)求解時間は安定しない
31387
41444
5739
6741

これより、重いインスタンスでは、マルチスレッドにしないほうが良い、と言えます。キャッシュに収まらないという、物理的劣化要因は、確かにありますが、deterministicでないということがあります。
deterministicにするかしないかは、パラレルソルバの設計要件です。しないことによって、共通リソースが多くなり、メモリ減少→キャッシュミス減少→オーバヘッドが少なくなる..パラレル化の効果がより強く発揮する場合もあり一概に駄目だとは言えません。

確率的な要因、determisticでないこと、キャッシュ溢れ、この3要因によって、シングルスレッドに劣るのだと思います。軽いインスタンスでもdetemisticでない影響はあるのですが、目立たないということでしょう。

<ハードのソフト化>
SC3では、求解オプションを追加しており、ハード列制約を緩和することが出来ます。
(解がないという事態を避ける目的で入れた新オプションです。Default Onです。)

ハード列制約のソフト化にチェックを入れると、最大ソフト重みの、およそ10倍の重みでソフト制約化を行います。上の左画面では、重み60までしかありませんが、右の結果画面では、重み1000の行があります。これが、ソフト制約化した擬似ハード制約になります。結果エラーが0ですから、ハード制約は全て満たしているという結果になっています。

このオプションで、走らせて見るとどの程度難しそうかは、求解の進み具合から、推測できるのではないかと思います。ハードインスタンスの場合、GO/NGですから、満たすのか満たさないのか、解が出てくるまで、あるいはタイムアウトまで、分かりませんが、上のようにチェック一つでソフト化
することで、先が読みやすくなるのではないかと思います。






 

2019年7月22日月曜日

メインソルバの改善 その2

マルチスレッド化の実装を行いました。

検証は、これからです。
cryptminisatの設計思想をそのまま拝借しました。マルチスレッド特有のLockに時間がかかってしまうことを避けるシンプルな設計思想です。

それから、名前がユニークです。似たような事は、私もやっていたのですが、体系的に少し徹底してやる感じです。メモリ削減に効果が期待できそうです。

さらに、新しい改善アルゴリズムを思いつきました。

以上を実装して、どれだけ効果があるかは分からないのですが、メインソルバについて出来る事は
やり終えたと思います。





2019年7月18日木曜日

メインソルバの改善 マルチスレッド化

アルゴリズム1は、メインソルバですが、実務問題では、やはり殆どの場合、他は使わない(使えない)、となると、やはりマルチスレッド化しておいた方が何かと都合がよいと思いました。

ということで、頑張って、マルチスレッド化と、及びチューニングを行い、なんとか旧来のパフォーマンスは、維持したいと思います。

 搭載ソルバ郡は、以下です。

アルゴリズム0/1は、SATベース、2は、UNSATベース、3は、SimulatedAnnealingの予定ですが、
未実装です。4は、数理的ソルバです。



     
名称略称停止方法CPU数内容
0SC2ソルバタイムアウト設定可ほぼ旧SC2ソルバです。
1メインソルバタイムアウト設定可リニア方式ソルバです
2特殊ソルバ厳密解が求まるまで停止しないので、打ち切るには、中止ボタンを押してください1実務問題は、殆ど解けません。
0近傍に解があることが分かっている場合に、有効な場合があります。
3Reserved   
4数理的ソルバ厳密解が求まるまで停止しないので、打ち切るには、中止ボタンを押してください1Simplex/内点法を使ったソルバです。実務問題では、殆どの場合、メインソルバに歩があります。しかし、学術ベンチマーク問題では、このソルバが優勢です。