2021年12月31日金曜日

HIGHSベンチマーク

 http://plato.asu.edu/ftp/milp.html

にHIGHS1.1.1のMILPベンチマーク結果がUpdateされています。このベンチマークでは、240問題を一定時間内に解きます。解けた問題数が一番下のsolvedで分かります。Gurobiが一番解けていますがこれはいつもの事です。

1threadと8threadが載っています。1threadについて見て見ると、scaledは、Gurobiを1としたときの時間比で、CBCは、8.59倍比ということになります。(Dec.30.2021時点のデータ)体感的に、もう少し差があるような気がするのは、解けた問題を対象にした時間比較だからです。解けない問題を何らかの方法で時間に換算すれば、差はさらに広がるでしょう。

8threadでは、HIGHS1.1.1が追加されており、CBCでは、約14.5倍、HIGHSでは、約13倍になっています。ですから、HIGHSの方が少しだけ良いという私のNSPでの計測結果と符合しているのではないかと思います。

=>https://schedule-nurse.blogspot.com/2022/02/highs.html

Mittlemanベンチマークについては、以下が参考になります。

untitled (orsj.or.jp)

COPTがMILPに参戦してきてそれなりの結果を残しています。こういう最適化領域の基幹的なソルバを設計する能力は、そのまま国力に通じる部分があると思います。(かってLSIを設計していたとき、その基幹的ツールである合成ツールは、Synopsysのデザインコンパイラという米国製が業界を席巻していました。ネーミングセンスがありますね。)

SCIPのソースコード行数は、GCC並みの50万行だったように記憶しています。ですから、一足飛びに商用並みのソルバを期待するのは難しいでしょう。HIGHSは、CBCに比べれば、モダンな筆致で、かなりコンパクトに書けています。MIPソルバについては、ほぼJulianHall教授とLeona Gottwaldさんの二人で開発しているようです。(Leona Gottwaldさんのプリプロセッサは、SCIPでも使えるようです。少し読んでみたのですが、殆ど理解できませんでした。)ちなみCBCは、IBMにいたJohnForrestさんによる開発で、かなりのご高齢のはずですが、未だメンテされているようで頭が下がります。後継の複数の開発者(大学の先生方)もメンテされているので開発が途絶える心配はないと思います。

日本の商用ソルバとしては、NTTDATAのNuOptが有名です。残念ながらGurobi/Cplexと比較データはありません。



2021年12月22日水曜日

クラッシックベンチマークの評価 

 下界が分かるということは、素晴らしいことで、これ以上良い解はないことが解く前から分かります。最適化ソフトは、所詮は、探索をするものなのですが、どこまでやればよいのか、誰かが教えてくれないといつまでも探索を続けることになります。ところが、予めこれ以上良い解はないという値が分かっていれば、その値に到達した時点で探索を止めてよい訳です。(逆にそれを知りえないソルバでは、タイムアウトで止めるかユーザが止めるしかありません。)

クラッシックベンチマーク郡を再度評価していて、実は、このベンチマーク全ての厳密解を出せるソフトはGurobi/Cplexを含めて一つもない、ということに気づきました。

正確には、現在のスケジュールナースは出せますが一度の求解では、出力できませんでした。Algorithm3では、これを改善し、クラッシックベンチマークでは、全ての厳密解を一回の求解ボタンで出せる世界初のソフトとなります。これにより、実務的にも大方厳密解を出せるのではないか?と期待しています。

そこで、厳密解インスタンス率という、性能指標を提唱したいと思います。仮想的に世の中にある全てのベンチマークソフト郡、実務インスタンス郡を全て集めてテストしたときに、上界まで到達出来たインスタンス郡の比率を指します。

例えば、30secでは何%、60/300/600secでは何% という風にプロットしてみたらどうなるか、興味があります。実際それが、体感的な性能に一番フィットするのではないかと思います。

=>評価しました。

https://schedule-nurse.blogspot.com/2022/02/blog-post_16.html

2021年12月18日土曜日

HIGHSのMIPソルバ

 JullianHall教授がCBCよりめっちゃ速くなったぜ!と豪語していたので、少し評価してみました。確かに、CBCより速い場合もありました。小さいインスタンス用途には良いのではないでしょうか?

SchedulingBenchmarksでは、Instance4までは解けましたが、それ以上は厳しそうです。確か、CBCが数分で解けるのは、Instance3位までだったので、多少良くなっているような気もします。=>https://schedule-nurse.blogspot.com/2022/02/highs.html

ちなみに、現在スケジュールナースは、Instance6まで厳密解を数秒、Instance8までの厳密解を数十秒以内に出力でき、Instance15/Instance21/Instance22の世界記録を保持しています。またINRC2(Internatial Nurse Scheduling Competition2 )データでは、State Of Art MIPSソルバを圧倒し、全インスタンスのKnownBestValue(これまでの世界記録)を更新しています。また、Classical Benchmarksでは、全てのリニア重みインスタンスについて厳密解を出力できる世界初のソルバです。現在、他に出来そうなソルバは見当たらないので唯一無二のソルバになります。


2021年12月17日金曜日

マルチコア時代に性能を出すために

 処理を分割して、単純にマルチスレッドにしただけで性能が向上すれば何も問題ないのですが、大抵の場合ボトルネックがあります。それは、各コアのキャッシュに載るかどうかということです。単純に参照データがコアキャッシュ内に載れば何も問題はありません。その場合は、ほぼCPUコア倍に性能の向上が期待できます。問題は、載り切らない場合どうするか?ということです。その場合は、

1)なんとかして、データ圧縮する

2)シーケンシャルアクセスしかないようにする

の何れかの方法を取る必要があります。シーケンシャルアクセスしかほぼないのならば、数GBのデータであってもキャッシュは効きます。Simplexのマルチコア化が難しいのは、大規模インスタンスになると2)が難しくなるからだと思います。

シングルコア性能が頭打ちの時代ですが、より速く答えを出すというソルバに求められることは変わりません。未来永劫変わらない普遍的な要求だと思います。




2021年12月16日木曜日

Instance22世界記録更新

ようやく満足できる解が見つかったので承認申請しました。 Ryzen8cores 開発中のAlgorithm3で46992secかかりました。Search Spaceが10の18953乗です。最適解証明はできませんでした。

Instance22 LB:30240 UB:30244


2021年12月15日水曜日

Instance22世界記録更新

 UB:31161⇒30441 

に更新しました。未だ途中経過なので承認申請していません。(チューニングしながら行っており更新したらコード修正⇒再トライを行っています。)




2021年12月14日火曜日

AVX2検出

AVX2は、自作の Interior Point Methodを使っています。通常は、Simplexの雄CLPを使うのですが、大規模インスタンスINRC2 n0120w8 や、SchedulingBenchmarks Instance21以上では、Simplexより内点法の方が速度的に有利です。そのために切り替えていますが、万が一AVX2をサポートしないCPUであった場合に落ちてしまいます。通常の実務インスタンスで、この規模はほぼないと言えますが、Githubに上げるプロジェクトを駆動する場合もあるでしょう、そういった対策の意味で、CPUがAVX2をサポートしているかどうかを知る必要がありました。ありがたく、下記を使わせて頂いております。

https://gitlab.com/yoshimoto/cpuid/-/blob/master/cpuid.cpp

2021年12月13日月曜日

Instance22世界記録更新 By Algorithm3

 更新しましたが、未だ途中経過なので承認申請はしていません。

UB:31279⇒31161(Search Spaceがまた前回(Instance21)から上がって、10の18953乗になっています。)


今回は、Algorithm3によるソルバでの途中経過です。Algroritm3は、Near Optimalなアルゴリズムで、基本的に厳密解を保証しません。厳密解アルゴリズムは、Algorithm4ですが、今までの評価では、Algorithm3がAlgorithm4に精度的に劣るケースは発見されていません。また、Algorithm4では、instance21以上では、実質的にコンパイル不可能ですが、Algorithm3では、(解けるかどうかは別にして)コンパイルは可能です。また、実務的インスタンス、例えば池上ベンチマークもAlgorithm4ではコンパイルできませんが、Algorithm3では問題なくコンパイル可能です。まとめると、

Algorithm1:SAT系ソルバ
Algorithm4 :数理的ソルバ (コンパイル出来れば)速い 厳密解探索用、コンパイル出来ないことがある。
Algorithm3 :数理的ソルバ 汎用 Near Optimal。  Algorithm1で時間がかかる場合、精度と速度で有利(ソフト制約が多数かつ多数のソフトエラーが残る場合)。また長大規模(3ヶ月以上)または、大規模(100人以上)でも、Algoritm1より有利になります。コンパイル出来ないことはないことを目指している。(しかし、経験的に枯れたAlgorithm1レベルになるには1年以上必要)

CPUコア数が、多くなればなるほど、Algorithm3は有利となります。また、この条件下での学術ベンチマークでは、Gurobi/Cplex、AutoRoster含め他のソルバを圧倒します。

現在、Algorithm3についてベンチマークの評価とチューニング作業中です。
実務インスタンスについては、シフト系については、実装を完了していますが、タスク系については、未だ実装していません。また、ペア制約も現在実装未です。


       



2021年12月11日土曜日

量子アニーリングについて

組み合わせ最適化は、ナーススケジューリングを包括する広範囲な問題領域です。

「量子」と組合せ最適化に関する怪しい言説 ―とある研究者の小言― - むしゃくしゃしてやった,今は反省している日記 (hatenablog.com)

それでは、古典的数理的解法で、ナーススケジューリング問題はどこまで解けているか?ということを少し論じてみたいと思います。

ナーススケジューリングの黎明期は、メタヒューリスティクスによる解法が主で、タブサーチ等が用いられました。

その後、MIPソルバーの発展によって、Gurobi・Cplexを始めとする数理的ソルバは、従来の解を更新、なおかつ、そのうちの超大規模を除く殆どを厳密解として提示出来るようになりました。(INRC1・SchedulingBenchmarks) 

そこで、INRC2では、問題をより大規模にして、なおかつ問題を複雑にしてMIPソルバーでは解きにくい形態としています。実際、INRC2問題は、MIPソルバーでは、殆ど解けていません。(実インスタンス形態としては、インスタンスによるのですが、どちらかというと、INRC2に近い実感があります。)

現在、MIPソルバーで、かなり解けるようにはなったけれども、全てが解ける訳ではありません。また、MIPソルバー間、AutoRoster等のナーススケジューリングソルバ間でも、性能の差がある、というのが現在地になります。

それでは、StateOfArtのソルバで、一体どこまで解けているか?という問いに対する回答が、スケジュールナースⅢになります。

現在、スケジュールナースⅢでの数理的解法結果を一連のベンチマークとしてデータを採取中です。実務問題については、未だ課題が山積していますが、少なくともベンチマークについては、動いており現在公開に向けバージョンアップしたバージョンAlgorithm3としてチューニング準備中です。ちなみにAlgorithm2は、MIPソルバそのもので、10人以下でしたらそこそこ動きますが、あくまで商用でないMIPソルバだとこんなもんです、程度で殆ど実用的ではありません。Algorithm1は、従来通りで変わりません。Algorithm4は、バージョンアップしていますがAlgorithm3の特殊形態です。Algorithm3は、汎用化した数理的ソルバです。

Algorithm3が、ナーススケジューリング問題の古典的解法によるStateOfArtと言い切ってよいと思います(GurobiでもCplexでもなく)。

一つ指摘しておきたいことは、必ずしもMIPソルバが全能ということではなく、これは容易に解けるだろうと思われる小さな問題でも、MIPソルバで解けなかったり、意外に時間がかかる事例が散見されることです。例えば 

Benchmarks | What is Schedule NurseⅢ (nurse-scheduling-software.com)

で、GPost/GPostB,BCDT-Sep,WHPP,Valouxis-1、ikegami-3Shiftxx 等です。これらは、人工的・機械的にベンチマーク用として造られたものではなく、実務問題をモデリングしていることにご注意ください。GPostは、僅か8人ですが、数理的に解くのは難しい部類にはいります。

ベンチマークは、アカデミック上の特定の実装が有利に働くような意図が背景にあり、必ずしも実問題にマッチしていません。実務問題とは基本的に異なりますが、INRC2に関しては、シフト形態は別にしてほどよくハード・ソフト制約がブレンドされ実務用途に近いと思います。

どのようなインスタンスでも安定して、短時間にNear Optimal(Ex.30sec/1min) 、時間をかければ厳密解に到達できることが、ソルバに求められる要件です。

いずれにせよ、今後はスケジュールナースⅢが一つの指標になると言い切ってよいと思います。


2021年12月2日木曜日

CPU使用率計測

 思ったように超大規模でのマルチスレッドの性能が出ないので、CPU使用率をタスクマネージャではなく、ソルバ上で得ようと思いました。中々良いコードが見当たらなかったのですが、StackOverflowにありました。Windows用です。


#pragma once
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include "pdh.h"

#pragma comment(lib, "pdh.lib")

class Query {

    PDH_HQUERY cpuQuery;
    PDH_HCOUNTER cpuTotal;
public:
    Query() {
        PdhOpenQuery(NULL, NULL, &cpuQuery);
        PdhAddCounter(cpuQuery, TEXT("\\Processor(_Total)\\% Processor Time"), NULL, &cpuTotal);
        PdhCollectQueryData(cpuQuery);
    }

    operator double() {
        PDH_FMT_COUNTERVALUE counterVal;

        PdhCollectQueryData(cpuQuery);
        PdhGetFormattedCounterValue(cpuTotal, PDH_FMT_DOUBLE, NULL, &counterVal);
        return counterVal.doubleValue;
    }
};

使い方は、簡単です。omp forループ後に、 

Query q;

cout << q << "[%]" <<endl;

で表示されます。

2021年11月22日月曜日

Search Spaceとは?

AutoRosterの左下に表示されている Search Spaceは、どのように計算しているのかを、シフトスケジューリング界の重鎮Tim Curtoisさんに聞きました。

Concerning the 10^17367, I imagine that it is possible to assign any shift to any person on every day. This is a relaxation but the value is an approximation so the basic formula is:
(ShiftTypes+1)Days x Employees
e.g. for instance21 = 9182 x 100
But I convert it to a power of 10 using
10Log10(ShiftTypes+1) x Days x Employees

私の計算式でも、(Shifts+OffState)**(26weeks*7days*100Staffs)で、
(8+1)**(26*7*100)=1.635580016513425644305E+17367
確かに、10の17367乗となり一致しています。(この計算結果は、計算サイトによります。)

ここで素晴らしい点は、厳密解であることです。すなわち、21133より良い解がないことが証明できていることです。全宇宙の原子数は、1googol(1e100)以下とされているので、それよりも遥かに大きい探索空間での最適解であります。よく量子アニーリングで現在のコンピュータで計算すると何万年という表現が出てきます。確かに一つ一つの解を地道にチェックしていったらそうなりますが、現実のPCでも上記のような広大な探索空間での最適解が得られることもあります。(数時間のRunで得られていますが、同規模のどんな問題でもいつも得られるということでもありません。)さらに、量子アニーリングで、下界を得ることは難しいと思うので、当面シフトスケジューリングにおける数理的アプローチの地位は揺るがないと思っています。


2021年11月16日火曜日

5800XCPUクーラを変更

CPU温度が92度あったので、安物のCPUクーラを無限五に変更しました。

温度は収まりましたが、今度は、思ったようにマルチスレッドが動いてくれません。

恐らく、大規模では、3次キャッシュも効かなくてDRAMからの到着待ちが多数発生するためと推測しています。Instance22以上の超大規模(期間1年、スタッフ数50人以上)問題には、さらにアプローチの仕方を工夫する必要があることが分かりました。



2021年11月10日水曜日

グラフ圧縮

 Instance23以上では、Graphが重過ぎて64GBあるシステムに載りません。そこで圧縮して一旦Diskに保存し、使用時に伸張展開する方式としました。しかし、LZ4で圧縮してみると、圧縮率が75%程度と思わしくありません。そこで、ZSTDに切り替えてみました。すると50%程度と、2倍程度の圧縮率となりました。

void Roster::decompress_fm_disk()
{
	string s = get_depth_map_filename();
	ifstream fin(s.c_str(), ios::in | ios::binary);
	if (!fin) {
		throw std::runtime_error("can not open compressed file!\n");
	
		return ;
	}
	char* src = new char[compressed_size];
	char* dest = new char[decompressed_size];
	uint64_t elements = decompressed_size / sizeof(uint64_t);
	void* eptr = my_alloc.allocate(sizeof(dd_struct_base_value),elements);
	dd_struct_base_value* zptr = reinterpret_cast(eptr);

	try {
		fin.read(src, compressed_size);
	}
	catch (...) {
		throw std::runtime_error("Read Error while reading compressed file.\n");
	}
	fin.close();
	int dest_size= ZSTD_decompress(dest,decompressed_size,src,compressed_size);
	if (!dest_size) {
		throw std::runtime_error("Read Error while reading compressed file.\n");
	}
	assert(dest_size == decompressed_size);


シーケンシャルRead(6GB/sec)という高速SSDを用意してタスクマネージャで、観測してみると、なんと転送されている様子が観測できません。あっさりキャッシュされているという落ちでした。

なお、プレテストを行ってみたのですが、Instance22/23共、これまでのLBは、更新できました。


しかし、この現象は、メモリに比較的余裕があるInstance23のみの話です。Instance24では、載り切らないはずですので、観測できると思います。

2021年11月9日火曜日

ScheduleNurseⅢ breaks the world record of Instance15 in Scheduling Bechmarks

 ScheduleNurseⅢ has updated the lower bound of Instance 15 from 3829 to 3830. The upper bound is 3831, so only one step is required to reach the exact solution. Unfortunately, it took around 100 hours to get the value due to the enormous branching tree. I think that is the final answer of ScheduleNurseⅢ.




2021年11月7日日曜日

ScheduleNurseⅢ breaks the world record of Instance21 in Scheduling Bechmarks

 

LB=21133 ,UB=21133

Machine :Ryzen5800X 3.8GHz(8cores)

ScheduleNurseⅢ has found the optimum solution in the search space of 10th power of 16367! 

Many researchers have tried to solve the problem for the past seven years, but no one could not have solved it exactly. Then, finally, ScheduleNurseⅢ made it.


2021年11月6日土曜日

ScheduleNurseⅢ breaks the world record of Instance15 in Scheduling Bechmarks

 Applying a new branch algorithm, I found the new record on instance 15 in scheduling benchmarks within 20minutes.

Machine:E3-1226V3 3.3GHz

I ran several hours, but I could not find any better solution beyond 3831.

It looks pretty long-running will be required to update the current lower bound 3829 because the branching tree is enormous. 


2021年11月5日金曜日

Instance20速度改善

 これが一連の改善シリーズ最終版の結果となります。


マシン:E3-1226V3 3.3GHz

改善前:2023sec

改善後:1353sec

Branch方法改善によるものです。Gurobi/Cplexとも比較してみました。



Gurobiは、厳密解に到達しましたが、Cplexは、到達しませんでした。(JobTimeout) この傾向は、Instance13でも見られました。Gurobiは、計測する度に速度を上げているので、数年後には、追い越されているかもしれません。




2021年11月4日木曜日

Branching Treeの可視化

 Algorithm4のデバッグをしていて必要になったので作りました。定番のGraphVizで可視化しています。このツールは、Verilog Simulatorでもお世話になっていて使うのは10年振りくらいです。



Instance8のBranching Treeです。このインスタンスの厳密解はLB=UB=1300が知られています。Branchingを行うのは、最適解、すなわち目的関数値が最小になる整数解を得るためです。連続変数での緩和解は、ROOT Nodeの値1296.57として得られています。





で、Branchingを行って、それまで得られた最小の整数解以上の目的関数値だった場合、そのノード以下は調べる必要がないという状況が生まれます。これをPruneすると言います。PruneしたNodeでは、子Nodeがありません。たとえば、So Far UB=1300が得られている状況で、連続緩和解1299.1が得られたとします。重みの種類は1,23,100であるとすると、整数解の目的関数値は1300が有りえる値です。その値は既に得られているので、もはやそのNode以下は見る必要がない、ということになります。





そう風に、ありえる全てのノードを調べて最適解を探します。一般にNodeを下降していくと、LBは上がって行きます。あるレベル(段)では、もうこれより小さなLB値は有り得ないということが分かります。そうすると全体のLBも上げることが出来ます。また、Prune効果によって、調べるべきNode数も減少していき、ついに調べるNodeがない(Empty)状態になったとき、LB==UBの証明、となる訳です。




組み合わせ最適化で爆発するのは、このBranching Treeが調べても調べてもNodeが増え続ける一方という状況です。こうなると有限の時間内に最適解を見つけることができないので、LBとUBの間にGapが生じたままになります。よく論文でGAPが何%以下になった、という記述がありますが、これは、調べるべきNodeをEmptyに出来なかったという裏返しでもあります。

LBに近いLBが最初から分かっていれば、PruneできるNodeが増えて、結果的に調べるNode数を減らせるので嬉しい状況です。その目的の為、ヒューリスティクス解を使うのも良くやる手法です。また、出来る限り早期にLBに近いUBを得たいので、最初はDFS(Depth First Search)を行うのも常道手段です。

こういった手順を踏むので、最初の実行可能解が得られる時間が長いのがAl4の特徴です。また得られる整数解は、離散的にしか得られません。(AL1みたいに一個一個減りません)

しかし、Al1では難しいインスタンスでも、時間をかければ厳密解に到達する可能性が高いのが特徴です。今回のRefactoringは、昨今のManyCore環境を生かしたコンセプトになっており、コア数が多ければ多いほど高い能力を発揮します。コア数が増え続けるのは今後も変わることのないトレンドでしょう。主体はAL1で変わらないとは思いますが、AL4を使う場面も多くなってくると予想しています。

2021年11月3日水曜日

塾時間割りGithub

一連のプロジェクトファイルをUploadしました。

 Schedule_Nurse3_Gallery/Japanese/プロジェクトサンプル/タスク勤務表/塾時間割 at main · sugawara-system/Schedule_Nurse3_Gallery · GitHub

にOriginalを含めてExcelファイルも同封しています。

プロジェクトファイルだけでしたら、スケジュールナースⅢでもダウンロード可能です。

    ファイル⇒Githubプロジェクトを開く

で、下記画面となります。塾時間割フォルダにあるファイルを選択してダブルクリックです。



プロジェクトファイルをロードした状態では、プロジェクトファイル名がついておりません。求解する前に名前を付けて保存してください。


今後、ユーザContributionプロジェクトファイルを拡充していこうと思います。

2021年11月2日火曜日

塾の時間割作成問題その3

 求解して、下記のように、右クリック、全て挿入で、1限、2限..毎、国語、数学、英語の講師数が表示されます。


<シフトとフェーズの関係>

設定⇒フェーズ定義、シフト定義、予定入力をクリックすると下の状態になっています。

シフトWorkの定義は、1限から4限までフルに働くパターンを表しています。

PH13は、1限から3限まで、PH24は、2限から4限までの3単位の連続時間業務を表しています。

PH12,PH23,PH34は、2単位の連続時間業務を表現しています。4個のあらゆる組み合わせを考えると4C4, 4C3,4C2,4C1のパターンが考えられます。必要ならここでパターンを増やしてもよいし、不必要ならパターンを削除すればよいです。とりあえず、defaultのまま話を進めます。



Workシフト(ラベルW)には、必ず4個のタスクで埋める必要があります。(必ず埋める必要があるので、空きタスクを前に定義しました。)また、PH12シフトでは、1限から3限まで3個のタスクで満たされる必要があります。

<予定は未だ入力されていない>

元のExcelでは、

となっていますが、未だ入力されていないことに注意してください。ソルバは、入力がフリーであるとして、解を求めています。つまり、上記予定が入っていないので、真の欲しい解にはなっていません。

<上を入力しただけでは不十分>
安藤さんは、すべてフルタイムだからWで埋めればよい、朱沢さんは、月水金に、34限だけなので.. という風に手で変換しながら入力したのが下です。

これで求めた解が下です。

確かに、予定が入っているシフトには、全て何らかのタスクが割りあてられていますが、それ以外にもシフトが入っているところがあります。スケジュールナース上の予定は、予定固定の意味です。入っていないところは、フリーです。ですので、上のExcelに対応させるには、休みシフトを定義して入力 求解して、

とすることが必要です。
ようやく、これで、所望の解を得ることが出来ました。





塾の時間割作成問題その4

 <ハード制約とソフト制約>

必ず実現するべき制約をハード制約といいます。一方出来れば、かなえたい制約をソフト制約と言います。ハード制約を満足できる解が発見できないときは、解そのものが出ません。ですので、ハード制約は必ず実現できなけれいけない制約でもあります。

今回の塾問題の場合、何があっても、受講者には必ず講師が割り当てられないと考えると、各時限の講師者数はハード制約となります。一方で、講師側のシフト希望も現状ではハード制約なので、容易に解がない状況が考えられます。スケジュールナースの場合、予定も含めて殆ど全ての制約がソフト制約化が可能になっていて、求解での様子を見ながら変えることができます。とりあえず、列制約をハード制約化したのが、下です。Defaultでは、ソフトレベルが定義されていますが、それをクリアするとハード制約になります。


<空き時間を最小化する>

行制約の空きタスクをパターン禁止にします。これがハード制約だと、当然解が無くなってしまうので、必ずソフト制約にする必要があります。ソフトレベルは、インデックスであり、重みではありません。インデックスに対応した重みは、求解時に指定します。


<求解結果>

画面左上行制約1が、上のインデックス1に対応します。チェックがブランクになっていると思いますので、チェックを入れます。重みは1のままで結構です。


結果、Errorsが29、Cost(目的関数値)が29となりました。結果か出方から見て、これは、厳密解で、これを下回る解は存在しません。

<行制約:1の適用を外してみる>

チェックを外すとそのソフト制約は、制約そのものがない、として扱われます。そうして、求解すると、目的関数値はソフト項がないので出てきません。で、空き時間を地道に目で数えていくと、同じ29個ありました。

<結果の解釈>

ソフト制約化によって、パターンを禁止したのですから、目的関数値が最小になる方向に作用するはずです。その効果がなかったということは、恐らく、シフトを固定にしているために、改善の余地が殆どない、ということではないかと思います。

<改善の余地 シフトor休み入力>

シフトは、何らかのタスクが埋め込まれる必要がありました。現状の予定では、シフトが空きタスクで埋まってしまうことがあります。そこで、予定の入力の仕方を変更し、予定自体は、ハード制約のままですが、例えばWまたは休みという入力の仕方に変更します。こうすれば、空きタスク最小化の効果により、休みシフトになる場合も出て来るでしょう。


上がその結果で、目的関数値は、21まで減少させることが出来ました。また、行成約:1のチェックを外して、制約を無効化すると、空き時間は、25程度となりました。よって最小化の効果が出ていることが確認できました。なお、結果から見てこれも厳密解だと思われます。

以上でこれが、空き時間最小化の解です。(同じ目的関数値の別解も容易に得られます。)















塾の時間割作成問題その5

予定入力付きのシフトの最小化は、前回でその答えは出ています。

そのままでは、自由度が少ないので、全くフリーの状態では、どのような解になるか、興味があったのでやってみました。

やり方は、簡単で、予定入力をクリアすればよいだけです。

さすがに、空き時間は5個と少なくなりました。しかし、決して0にはならないということが分かりました。

<なるべく連続シフトで>

空きタスクをなるべく挟まない形を記述追加しました。


業務は、英数国の集合です。

結果は、


たまたまなのかは、分かりませんが上記解はありました。(本来はソフト制約とすべきでしょう。)

以上、スケジュールナースⅢによるハードおよびソフト制約化について見てきました。勤務表の観点は、雇用者側と、スタッフ側の要求と相反するものがあり、どの辺にバランスを取るかというのは、管理者次第です。制約化も千差万別であって、ある職場にとっての正解が必ず別の職場でも正解になるものでもありません。また組み合わせ問題の最適化という性質上、やってみないと(RUN)してみないとどんな具合か分からない、予想がつかない、という厄介な性質もあります。

スケジュールナースでは、このトレードオフ問題に関して、予定制約のソフトレベル化(予定に優先度をつける)あるいは、禁止化(希望を書くのではなく禁止を書く)、という提案を行っています。なるべく広い解空間で、なるべく良い解を探す、という発想です。

以上勤務表ソフトを使った塾の時間割作成の紹介でした。





塾の時間割作成問題その2

 前回Import用のExcelシートを作成しました。今回は、そのExcelファイルをインポートして、プロジェクトファイルを作成するところまでを行います。

タスク勤務表スキル付きプロジェクトを立ち上げます。


前回、整形したExcelファイルをインポートします。

ウィンドウの設定⇒Excel取り込み出力設定⇒Excel取り込み設定⇒ファイルパス

で、前回整形したExcelファイルMyタスク勤務表4phaseを指定⇒取り込みボタンをクリックします。


予定入力をクリックすると(隠れている場合は、ウィンドウズの設定⇒カスケード等で表示させる)次のように国数英の予定が表示されます。


なお、上のように数値部分が上手く読み取れない場合があります。その場合は、Excelからコピペしてください。



その他のプロジェクト設定変更点は、以下の青部です。

■ハード列基数制約のソフト化をオフ

■最終タイムアウトを 30⇒1

にしています。


求解ボタンを押すと1秒未満で、下記画面になります。



ファイル⇒名前をつけて保存

でプロジェクトの完成です。




塾の時間割作成問題その1

 https://qiita.com/e-yudana/items/dab6bc76d9ff41d551f5

を解いてみます。

スケジュールナースⅢにこの問題をどのようにマッピングさせるかが、まず最初の問題です。

講師の勤務希望は下のようになっています。1日を4Phaseに分けると良さそうだという

ことが分かります。



また、担当科目は、

となっています。ということで、フェーズ-タスクタイプの勤務表にすれば良さそうだ、ということが分かりました。

ゴールがあった方が分かりやすいと思います。
下記が実装したプロジェクトの様子です。

イメージし易くなったのではないでしょうか?

月から土まで、1限から4限まで、必要な人数を過不足なく確保すればよい、という問題です。
ただし、国語とか数学のスキルが必要なので、スキルを持った人を確保する必要があります。また、その人数は、各日、各限で違います。
この問題は、たまたま、受講生と講師が1-1でマッピングされるので、この形式にマッピングできました。(受験生と講師のマッピングは、ほぼ自明扱いとしています。。受験生の名前は、入力不要です。)

 現スケジュールナースⅢのユーザは、大半がシフトタイプタイプですので、少し奇異に感じる方もいるかもしれません。フェーズタスクタイプ型というのは、1日のうちで、複数の仕事を行う場合に適した勤務表です。予定が、タスクと、シフトと二つあるのが特徴です。マニュアルはこちら

Pythonは、全く使っていません。GUIのみで解くことは可能です。

問題は、

どのようにしてExcelから上記プロジェクトにマッピングするか?

です。最も近いExcelは、タスク勤務表4Phaseとタスク勤務表2Phaseスキル付きです。
これらを作業フォルダにコピーしておきます。下記はインストールしたスケジュールナースⅢで、ファイルを開くで、全てのファイルで、Excelファイルを表示させています。


タスク勤務表4Phaseを編集します。最初は、スタッフ名です。


次に稼働日です。月曜から土曜なので、2021年11月1日-11月6日に設定しました。

表示開始日は制約開始日にしました。不要な予定はクリアします。


<タスクスキル属性>

このシートは、タスク勤務表4Phaseにはありません。タスク勤務表2Phaseスキル付きからコピーして、次のように編集します。空き時間は、その名の通り空き時間です。通常の、業務形態の場合、なんらかのタスクで埋められるのが普通ですが、このプロジェクトの場合、空きタスクを定義しないと、解がない状態になってしまいます。全てのスタッフがこのスキルを持つ必要があります。


<工程人数>

編集して以下のような表にします。


手で行うのも大変なので、受講管理表データをExcel内で合算して、それをコピーするようにしています。








以上で、整形したExcelをインポートする準備が完了しました。

*その2からその5まで解説はあります。
GithubにオリジナルのExcelファイル、使用したExcelファイル、プロジェクトファイルを置いています。

2021年11月1日月曜日

時間割り作成問題

 池上先生のチュートリアル論文が参考になります。

untitled (orsj.or.jp)

現状では、CPLEX/Gurobi等の数理的ソルバーを使って解くことは難しく、ヒューリスティクスが主体みたいです。また、時間割について競技会(Timetabling Competition)も過去5回行われています。(NurseSchedulingCompetitionは過去2回)

PATAT - International Conference on the Practice and Theory of Automated Timetabling (patatconference.org)

スケジュールナースは、時間割のソルバーではありませんが、タスクや、Pythonを用いることで、簡単なモデルでしたらモデル化できるかもしれません。前回もそうでしたが、スケジュールナースは、単純な勤務表のみに留まらず、既に、工場の生産計画、人材派遣業務、放送局のシフト割、等でも使われています。数独も応用のうちの一つですが、時間割もその一つになるかもしれません。

Qiitaで、面白そうな問題があったので、解こうと思っていたのですが、世界記録更新の方に眼がいってしまい手付かずになっていました。Algorithm3ソルバーは、基本アルゴリズムが完成しつつあり、検証のための時間待ちが多くなってきました。空いた時間で、この問題を解いてみたいと思います。


2021年10月31日日曜日

看護実習科目の年間スケジュール表の作成-GUI編

 前回、シフト連 成人1>成人2 を全スタッフについて制約するコアアルゴリズムをPythonで記述しました。今回は、任意のシフトの連順をGUIで操作できるように、GUIとPythonの記述追加を行います。

 下図は、シフト連の設定画面例です。スタッフ名1Gでは、成人1>成人2>老年>母性>地域>精神>小児>統合 の順でシフト連順を設定しています。その他のスタッフでは、成人1>成人2のみに設定する画面となっています。 

これにより、任意のスタッフに任意のシフト連順を設定することが出来ます。さて、スタッフプロパティでこのように設定するためには、スタッフプロパティ属性を記述しています。


つまり、

シフト連名=シフト名+'_'+連順(1,2,3,4,5,6,7,8)

としています。ルールです。このようにするのは、スタッフプロパティアイテム同士で、名前が衝突しないようにするためです。注意する点は、以下の2点です。

■シフト名と一致しないこと

■連順同士で区別できること

Python上で同じ名前になってしまうと意図しない動作となってしまい為です。(エラーは出ません。)

設定が多く面倒そうですが、テキストエディタで1行を記述しておいて、コピペ、置換、コピペ..で行うと、それほど面倒でもありません。



RUNした後、ソース全体を見ると、下のように成人1と、成人2には、全スタッフ[0,1,...]が設定されていることが分かります。また、老年は、スタッフ1Gである[0]だけが設定されていることが分かります。


よって、これらをPythonで拾ってくれば、GUIの設定を拾うことが出来ます。

<メンテナンス性を上げる>

Pythonソースを見ると特定のシフト名に対する記述がありません。今後のシフト名の変更、追加では、Pythonソースをいじらなくて良いようにしています。(プログラムは、書いたときは覚えていますが、1年後は、初見と同じです。)シフト名の変更追加があったときは、スタッフプロパティのみを変更すればOKです。覚えておくべきルールは、ルールだけです。

以下がPythonで書いた全ソースになります。



import sc3
import re #正規表現

def get_sequence_shift(person,seq):
    for s in globals():#全ての変数名をスキャンする
        rs=re.sub('_\d+', '', s)#正規表現 sから'_数字'を削除する ルール参照
        if s !=rs and rs in shiftdef:#削除した名前がシフト名と一致するものがあるなら
            ss=rs+'_'+str(seq)    
            if ss==s:#要求連順Noと等しいなら
                if person in eval(s):#文字列を評価して要求personと一致しているならば
                    #sc3.print('person='+str(person)+' '+rs+'\n')
                    return rs #シフト名を返す
    return ''#要求に一致するものはないことを報告する


def 順序制約(person,shift1,shift2):#person シフト連名 シフト連名+1の制約を行う。どちらも空白ではない

    first_day=今月[0]
    last_day=今月[len(今月)-1]

    st=staffdef[person]+' 順序制約 '+shift1+' > '+shift2 
    sc3.print(st+'  を制約します。\n')
    for day in 今月:
        vlist2=[]
        vlist1=[]
        for d in range(first_day,day+1):
            v2=sc3.GetShiftVar(person,d,shift2)
            vlist2.append(v2)
        for d in range(day+1,last_day+1):
            v1=sc3.GetShiftVar(person,d,shift1)
            vlist1.append(v1)
        V2=sc3.Or(vlist2)
        V1=sc3.Or(vlist1)
        st_day=st+' '+ str(day)
        sc3.AddHard(~(V2&V1),st_day) 
 
def 順序():
    n=len(shiftdef)
    for person in 全グループ:#全スタッフについて
        for seq in range(1,n+1):#全シフトについて
            shift1=get_sequence_shift(person,seq)# 連1
            shift2=get_sequence_shift(person,seq+1)#連2
            if len(shift1)>=1 and len(shift2)>=1:#どちらも空白でないときだけ
                順序制約(person,shift1,shift2)#制約する
 
順序()

上記ソースで、get_seq_shiftが、ルールに基づいたシフト名を返しているルーチンになります。ここが、一手にGUIとのインタフェースを引き受けています。正規表現とかglobals()とか、私もいちいち関数名を覚えているわけではなく、ググリながらコピペすることが多いです。

制約部については、前のコアアルゴリズムを改造しています。

以上です。

<短く書ける理由>

意外に短く書けているのは、Python自体のライブラリが充実していることと、既にGUIで記述した中身がPythonで記述されているからです。(ソース全体を見ると、結構長いソースになっています。)

<GUIは、まとめ制約にすぎない>

普段、なにげなく記述しているGUIも、裏では、今回記述したみたいに、展開すると沢山のprimitiveなAddHardや、AddSoftが動いていることが想像できると思います。Python上の制約も、Engineの中では、区別がありません。仮にC++で組み込んだとして比較しても性能上の優劣はありません。

その気になれば、殆どGUIを使わずにPython主体に組むことも可能ですが、GUIで設定仕切れない部分だけをPythonで記述することをお勧めします。