2020年8月7日金曜日

2020年8月6日木曜日

Algorithm4のRefactoring

以前頓挫した、ペア制約のLP化を再考してみました。

A:f1(x0,x1,x2...)≤b1;
B:f2(x0,x1,x2...)≤b2;

Implication A→Bは、
!A+B
そのソフト化は、Binary Variable Cを追加して
!A+B+C >=1;-----(1)

Minimize:  ...+C*Cweight;

とします。ここで、Cは、0になるように作用することに注意します。すると(1)式より
!Aもしくは、Bが1になるように作用することが分かります。なので、
!A:  f1(x0,x1,x2...)+M(1-A) ≧b1+1;
   B:  f2(x0,x1,x2...) -M(1-B) ≤b2;
とすれば、A==1、B==1側に自然に作用します。(Mは、BigMです。)

上のように定式化すれば、ペア制約ImplicationもLP化(Linear Programming)出来そうです。



2020年8月4日火曜日

130Aをリリースしました

メジャーバージョンアップです。

今後(8月)の実装予定としては、
1)Algorithm4の一般化
2)祝日の国際化
3)マニュアル類の英語化
4)Dockerの構築

です。

2020年7月31日金曜日

ユーザマニュアル作成

作成しました。

PowerPoint→PDF→しおり作成→htmlで、しおり作成を手動で行うのがどうにも面倒だったので、PowerPointからタイトルを抽出するpython codeを書きました。

PowerPointからタイトルを取り出したつもりですが、なぜかページNoを拾ってしまうことがありました。良く分かっていません。htmlにしたときページが1ページずれるのも謎です。
import pptx
from pptx import Presentation
prs = Presentation("schedule_nurse3_user_manual.pptx") # load the ppt
slide_titles = [] # container foe slide titles
page=1
file = open('user_manual.txt', 'w')

for slide in prs.slides: # iterate over each slide
  count=0
  for shape in slide.shapes:
    if shape.has_text_frame:
      count+=1
      if not shape.text.isdecimal():
        if page !=1:
          file.write(shape.text+'/'+str(page-1)+',Black,notBold,notItalic,closed,FitPage\n') 
        print(page,shape.text)
        break
      if count>=2:
        break 
  page+=1    
file.close()
#print(slide_titles)

2020年7月30日木曜日

Excel予定シフト読み込みの変更

Excel Importの整理をしました。
ExcelImportのインポートを行う場合は、稼働日とスタッフ属性は、必須としました。
また、予定シフトの読み込みも、変更を行いました。従い、常に制約期間は変更禁止となり予定シフトで、制約期間が変更することは出来なくなります。

2020年7月29日水曜日

シフト型勤務表とタスク型勤務表

2日以上のシーケンスが発生するものをシフト型と分類しています。それ以外をタスク型としています。ナーススケジューリング問題は、シフト型です。

で、経験的な難易度でいうと、

タスク型 フェーズ数3以下 容易
シフト型 行制約でソフト制約がないもの 容易

それ以外は、難しい分類に入ります。中でも難問は、断トツにINRC2の問題です。行制約のソフト化がほぼ全制約に渡り、なおかつ複数のタスクがあります。行制約のソフト項がない、ScehdulingBenchmarkは、現在では、MIPソルバにより、殆どの問題は解くことができますが、INRC2の問題は、MIPソルバでは殆ど歯がたちません。敢えてそういう問題にしている意図があると思います。(作成者に聞いてみたことはありません。) 池上先生のベンチマークは、実現場での制約をヒアリングした実務問題で、実は、INRC2のソフト制約以上にソフト制約が入っています。というより全てがソフト制約で記述されています。通常制約により探索空間は減少しますが、全てがソフト制約で記述されているために、探索空間の減少はありません。その意味で難問の部類に入り、実際、数理的ソルバーでは梃子摺ります。しかし、解空間が広いので、数理的手段を用いない別なアプローチで難しくはありません。が、パラメータをちょっといじるだけで、最高難度の問題にもなりえます。つまり、実務上の問題も、容易に高難度問題になり得るということです。それには、探索空間と解空間の大きさが関係しています。探索空間が大きくても解空間が大きければ、解は容易に見つかります。一般に、探索空間が大きく解空間が狭い問題が難問です。