Q.勤務時間を制限する条件は使用しない方が良いのでしょうか

 Q週に35時間制限など、看護補助者向けの時間制限条件を希望される病院が多くなってきています。

Ans.

必要であれば、使って構いません。ただし、

■時間よりは、回数制限の方が求解時間では有利になります。

■時間制約はハード制約のみです。ソフト制約はありません。

なので、可能であれば、回数制約で記述可能ならば、回数制約にすることをお勧めします。

Q.設定した条件の並び順で解が出るまでの時間に変動したりするのでしょうか。

 Ans.変動がないとは言えませんが、その程度は、制約追加よりは、小さい程度ですので、通常無視できると思います。

Q.行制約が多ければ多いほど、自動作成の時間もかかる認識に相違ございませんでしょうか

 Ans.はい。一般的には、解空間をより狭めることになるので、そういう傾向にはなります。より詳細には、問題の解領域には、二つの領域があると考えられます。

■一つは、SAT空間

■もう一つは、Optimize空間です。

言い換えるなら、SAT空間は、Hard制約空間です。問題は

■Hard制約を全て満たした上で、

■最適解を得る

二つのステップからなることに注意します。

題意は、明らかにHard制約空間を狭めることになると思うので、SAT解/探索空間比を狭めることとなり、探索時間はよりかかる、ということになります。

一方、Optimize空間、言い換えるとSoft制約空間の観点でみると、必ずしも上記傾向にはならない、ということが言えます。

ハード制約主体のインスタンスならば、より時間がかかる傾向となりますが、ソフト制約主体のところに、ハード制約が追加されると、解空間を狭めると同時に探索空間も狭めます。結果、SAT解/探索空間比が大きくなれば、より解を見つけ易くなる方向に作用します。

よって、ソフト制約主体のインスタンスでハード行制約を強化する記述を追加すれば、むしろ時間節約になる可能性が高くなります。ソフト行制約を追加すれば、やはり時間は増える傾向になるでしょう。

結論として、一般的な傾向としては、確かに、制約追加により時間が増加する認識は間違っていないと思いますが、ハード制約・ソフト制約によってその意味と作用は異なります。

まとめとして、

■ソフト行制約追加ならば、時間は増える

■ハード行制約追加ならば、

　●ハード制約主体のインスタンスなら時間は増える

　●ソフト制約主体のインスタンスなら時間は減る可能性がある

Q.ハード制約矛盾でも解が出るようにして欲しい

 Q.必須条件が違反していると自動作成できないのが現在のソルバだが、必須の条件も許容して自動作成できるようにしてほしい

Ans.

これは大変難易度が高い問題です。上記を言い換えると、

１）絶対守らないといけない制約同士の矛盾を緩和して

２）解があるようにして(make feasible)

３）最適化(optimization)

ということを行うということと同じことです。実は、AL1の原因解析機構は、上記そのものを行っています。ですから、既にやれることはやっている、とも言える訳です。

実は、この問題、昔から指摘しているのですが、誰も手をつけようとしていない学術問題で、恐らくはNP困難な領域だと思います。緩和解は無数にあり、どれが最適かは、さらに難しいと思います。

make feasibleの部分に関しては、AL1とは別にAL3のアプローチも考えられます。

詳細を、今、述べることは出来ませんが、AL1での弱点を補うアプローチは考えることが出来、それはAL1自体では、実現不可能ということです。つまり、全く別のソルバが必要になる、という大変に大きなテーマとなります。現在、AL3の根源的な再設計・研究開発を進めており、これが終わり次第、上記テーマに取り組みます。長い時間がかかって申し訳なのですが、次世代でのアルゴリズムとして組み込みます。

Q,解が思い通りの挙動にならない

 Q.今月に関して13日の午後のみ4名全員出勤にしたいと思いまして、いつも決まっている列制約の3行目：月火水の午後は3名をソフト制約にして、28行目の全員出勤日は午後4名をハードにしたところ、どうしても12日の午後が2人になってしまい、思い通りの挙動になりません。

この時々ある特別な変更はどう設定すればよいでしょうか？

多分、スタッフの行制約との絡みなのですが、もしそうなら、人数の方を優先して解が出ないようにして、スタッフ側で調整したいのです。

Ans.

まず、考えられるのは、想い描いている状態が、ハード制約上の矛盾を孕んでいる可能性です。

現在の状態を確認しました。

確かに12日が2名になっております。

１）月火水の午後は3名をソフト制約にして、

２）28行目の全員出勤日は午後4名をハードにしたところ、

３）どうしても12日の午後が2人になってしまう

そこで、まず、ソフト制約化した制約をハード制約に戻しました。

すると、解のない状態となりました。解要因の日が12日だけではないことから、12日以外で、解がない事態が考えられます。そこで、原因を分離するために、12日だけに効くハード制約を記述しました。

これで求解してみると、やはり解が無い状態が再現します。

このことが意味しているのは、12日にだけ効く制約と矛盾がある、

■12日の午後が3人

■13日午後4名

が物理的に相いれない状態になっている、ということです。上にその要因が列挙されています。試しに、5連休関係の制約を無効または、ソフト制約化してみます。

こうすると解がありました。

あるいは、関係する予定をソフト化します。

このようにして、要因として列挙されているハード制約をソフト化することで、目的のハード制約を満たしたまま、解を得ることが出来ます。

その他にも要因は示されているので、別な緩和策はあると思います。以上が、とりあえず、ご要求を満足させるやり方の例になります。緩和策は、実は無数にあり、何が適切な緩和かは、管理者だけが知っているので、ここではあくまで例ということでご承知ください。

＜この時々ある特別な変更＞

ｘｘさまのプロジェクトは、通常のプロジェクトとは異なります。通常は、ハード制約を設定したらそこの制約はいじりません。それがルールということです。ところが、小人数であるが故だと思いますが、そのハード制約を変更の変更が元で大変な変更になってしまっています。通常スタイルでは、ルールを決めたら（ハード制約を決めたら）後は予定のソフト化で対応するのが基本です。（推奨している記述スタイルです。）

予定の方をハード制約とするとその都度、制約を見直す必要になることはご承知の通りです。

ｘｘさまのプロジェクトは、色々なノウハウが詰まっていて、私がどうこう出来るプロジェクトでは、もはやありません。

スタッフの予定を最優先のハード制約とするなら、列制約・行制約共にソフト制約化すべきでしょう。大事なことは、何をハード制約するか？です。これがぶれると、土台を弄るようなもので、しばしば大変な変更を伴ってしまいます。

まとめとして、

■上記の観点も盛り込み、

■今回のような機に、整理統合を心掛けながら、

■プロジェクトを鍛え育成して頂けたら、

さらに使い易くなっていくのではないかと思います。

ラベル設定法 先は未だ長い

 ようやくInstance13で、ラベル設定法によるLBが出るようになりました。下記は、LB＝1348までに到達するまでの時間比較結果です。

label setting algorithm:83sec

Current AL3:117sec

恐らく、幾多の研究者が、Instance13での求解に手間取った筈で、ラベル設定法によるLB解の提示が行われたのは、世界初と思います。ラベル設定法は曲者でして、数々の関門があります。その関門をくぐり抜けた者だけがInstance13のLB解に辿りつけます。ここまで来るにもかなり苦労しました。

しかしながら、さらに数十倍の巨大なインスタンス(instance22/23/24)に対しては、現在無力です。具体的には、

１）ラベル数の爆発が抑えられていない

２）求解時間がかかりすぎる　Instance23で300sec -3600sec/iteration

３）メモリ所要　11GB/roster

目標は、60sec/iterationですから、あと60倍程度高速化しないと使い物になりません。控えている改善アイデアをさらに投入すれば、なんとかなるだろうと見ていますが、それも未だ分からない、といった状況です。ちなみにMIPソルバによる求解では、2000secを下回ることはありません。

Q.制約が効かない

 Ｑ．新職員のｘｘに拘束の翌日の拘束はダメというパターン禁止（ｘｘの行制約7行目）と拘束回数（行制約31行目）をハード設定しているつもりなのですが、結果としてどちらも守られていないです。何か設定の間違いがあるか教えていただけると助かります。（5月9日10日が連続になっています。）

Ans.

当該スタッフの解が表示されていません。よって、制約が効かないのは、グループ定義廻りが問題である可能性が濃厚です。

マウスホイールボタンを押して当該集合を確認すると空集合になっています。誰も選択されていないことが分かります。

スタッフプロパティシートを見ると、誰も設定がされていないことが分かります。原因が確定しました。

設定して、求解、解の確認をして終了です。