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.

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

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

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

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

Q.GW中の出勤設定でハードエラー

 Q.5/1は金曜日で、基本設定は午前3人、午後2人の設定なのですが、GW中ということもあり、午前も午後も3人に設定したいと思いました。

強制3人出勤日という列制約を作り、強制平日扱い日という曜日設定を割り当てました。

すると以下のようなエラーがでました。確かに金曜日の午後の制約内容が2つになるのでこのエラーは分かるのですが、このような場合に

どちらかを優先するような設定方法を教えていただけると幸いです。

 ●エラーがあります。ハード制約の問題かソフト制約の問題かを切り分けます。

Algorithm 1 Solving Process Started..

●ハード制約に問題があります。

Algorithm 1 Solving Process Started..

o 1   0.390000(sec)

Python プロパティファイルの生成が終わりました。

o 1   0.699000(sec)

●次の組み合わせが充足していません。

● 列制約グループ1.強制3人出勤日午後3人 2026-05-01

● 列制約グループ1.木金の午後は2人 2026-05-01

Ans.

5月1日で、木金の午後は2人と、強制3人出勤日が矛盾しているので、どちらかをソフト制約とします。今、木金午後2人をソフト制約にしたとします。ソフトレベルを5に設定しました。ソフトレベルは、何でも良いのですが、他に使用していないレベルにしました。

設定すると求解ページの適用がチェックされていない、列制約レベル5が現れます。✓をしないと、このソフト制約は無視されてしまうので、✓をして求解します。

解を確認します。ソフト制約化した方は、色がつきソフトエラーとなっていることが分かります。

以上です。

次世代用の重み設定

 来年度，新ソルバの投入を予定していますが、重み設定は、１～１０までを推奨します。これを超えても、問題になることはないと思います。が、記述スタイルとして、下記のような書き方をされている場合は、改めるようにしてください。

新ソルバでは、重みに幅があると（上の例では、1－1000000）安定性に問題を生じる可能性があるので、なるべく1－10の範囲に収める