COPTに評価ライセンスの延長を要請

 半年のトライアル期間に解くことは、出来ませんでした。この間、ほぼこの問題を解くことだけに集中してきたのですが、力及びませんでした。ただし、この研究期間に発見した二つの新しい方法を使えば、可能性は出てきました。そこで、COPTにライセンスの延長をお願いし，挑戦を継続することにしました。

Dear COPT Support Team,

Thank you very much for your continued assistance and for providing access to the COPT Optimizer.

Over the past six months, I have been using your solver to tackle the final remaining open instance (instance24) in the following benchmark:

https://www.schedulingbenchmarks.org/changes.html

However, the research has taken significantly longer than originally expected, and I now require additional time to complete the work.

Therefore, I would like to kindly request a six‑month extension of my evaluation license.

Once the instance is successfully solved, I plan to publish a research paper that will properly cite and acknowledge the use of the COPT Optimizer.

COPTからは、subscriptionを勧められましたが、それは考えていないことを伝えました。

Dear COPT Support Team,

Thank you very much for your continued support and for your kind offer to discuss subscription options.

At this time, I am not considering a subscription license. For my practical, real‑world instances, solvers such as CLP, HiGHS, and CuPDLPx are fully sufficient. In fact, except for the very last remaining open instance, I have been able to solve all unresolved academic benchmark problems using these solvers.

However, the final instance is exceptionally large, and based on my experience, it is extremely difficult to handle within a reasonable time frame without the performance of your solver. This is why I have been relying on COPT specifically for this last challenge.

Thank you again for your understanding and for taking the time to consider my situation.

Dualの具体例

 例えば、累計シフト制約で、累計シフト数≦１０であったとします。

この時最適解が、累計シフト９であったとすると、

■そのDualは、０

となります。つまり、制約境界10に接しておらず、余裕（スラック）が１あります。この制約を微小に変化されても目的関数は変化しません。よって、制約に対する目的関数への寄与は0、ということになります。

では、MIN側にも制約があった場合は、どうなるでしょうか？　６≦9≦10　の場合も余裕があるので、

■そのDualは、０

となります。

もう一つ制約があって、特定シフト回数≦３　と言う制約があって、最適解時の回数が3であったとします。こういう境界に張り付いた状態であるときだけ、Dualは、0にはならない、ということが出来ます。逆に言うと、Dualが0である制約は、効いていない、ということになります。

　

注意すべきは、Dualの概念が有効なのは、あくまでLPsolver上のみです。即ち緩和問題でのみ定義可能です。整数計画では、DUALという概念はありません。

Dualの考え方

 久保先生の著書中、「最適化理論に関するプロとアマの違いは、双対性や、相補性の意義を理解し活用できるかどうかである」、とあります。私自身、双対性に関しては、完全に使いこなしている訳ではないのですが、最適化を実装する上においては避けて通れません。

DUALは、目的関数ー制約が表裏一体の関係にあるという考え方です。最適化と言った場合、

■制約違反のペナルティ量を最小化する、目的関数の値を最小化すること

■制約を緩和―厳しくすること

は、独立していなくて関係がある、と言うことを示しています。一般にSimplex法で解く場合、Primalで解くかDualで解くかは、指定があります。問題を解くのに、二つのやり方があって、どちらで解いても答えは同じになる、ということでもあります。（しかし、求解時間は一般的にインスタンスにより異なる）

＜リソース制約が効いているかどうかを判定することが出来る＞

例えば、次は、Instance13のログです。

上のログは、COPTが２１３msで解けているにもかかわらず、ラベル設定法では、８９秒もかかっていることを示しています。このとき、row priceの項がDualの値を示しています。

このDualは、制約に対する値で、下の累計制約に対応しています。上で最初の項は、Pythonで書いたWeekEnd勤務の累計、2番目の項は、下の最初の時間和制約に対応します。

ここで重要なのは、Dualが０だとその制約は効いていないことを示している、ということです。殆どのDual項は、0であり、実際に効いているのは、ほぼMIN-MAX時間制約のみ、ということが分かります。

ラベル設定法のドミナンスとは？

ラベルとは、RCSPにおいて、経路状態を表現する言葉です。

ドミナンス（Dominance：支配）とは、「ある経路（ラベル）が別の経路よりも明らかに優れているため、劣っている方を探索から除外する」という判断基準のことです。

不要な探索の削減（枝刈り）

あるノードに至る2つのラベル  とを比較したとき、全ての指標において、同等以上に優れていて、少なくとも一つが上回るとき、Pruningできます。

もし  がすべての指標（コスト、時間など）において  以上に優れており、かつ少なくとも1つの指標で  を上回っている場合、「 ｘは  ｙを支配(Dominate)する」と言います。

支配されたラベル  は、その先をどのように延長しても  を延長した経路より良くなることはないため、それ以上探索する必要がなくなり、破棄されます。

＜Min制約をどうする？＞

ラベル設定法や動的計画法において、MIN制約（「〜以上でなければならない」という下限制約）をMAX制約（「〜以下でなければならない」という上限制約）に変換する一般的な手法は、「残りの必要量」に着目する、または「変数の反転」を行うことです。Max制約になれば、「とにかく小さいほうが良い」というDominate　Ruleで枝刈り出来ます。

具体的には、以下の2つのアプローチがよく使われます。

1. 「残りの必要量」を状態変数にする（推奨）

「現在の蓄積量」を管理するのではなく、「目標達成までにあとどれくらい必要か」をリソース（ラベル）として管理します。

変換前（MIN制約）:

状態：現在の合計値 

制約： （ 以上のリソースが必要）

変換後（MAX制約）:

状態：残りの必要量 

初期値：

各ステップ：リソースを消費するごとに  を減らす（0以下になったら目標達成）

制約：なし（または  が 0 になることを目指す）

これにより、「下限値を突破する」という条件を、「初期値（上限）から減らしていく」というMAX制約に近い形に落とし込めます。

2. 変数の反転（ネガティブ変換）

単純に符号を反転させる方法です。

変換前: 

変換後: 

ラベル設定法のアルゴリズム内で「リソース消費量」を正の数で扱いたい場合は、「余裕（スラック）」を定義します。

＜問題はMIN-MAX制約＞

MIN-MAX範囲がある場合は、注意が必要で、同じリソースに対して、異なる方向にドミナンスが働くことになります。そのまま実装すると矛盾した枝刈りとなり最適解を失い、最悪は、Infeasibleな結果となります。

単純に、MINまでは、大きいものが強い、MIN以降は、小さいものが強い

とすれば、良いような気がします。しかし、そのロジックで単純に片方を捨ててしまうと、厳密解（最適解）を失う可能性が非常に高いです。

なぜなら、ラベル設定法におけるドミナンスの鉄則は「将来のいかなる拡張に対しても、一方のラベルがもう一方より必ず良い結果をもたらす」と言い切れるときだけ、劣る方を捨てるというものだからです。「Minまでは大きい方が強く、Min以降は小さい方が強い」という切り替え方式では、「将来どちらの制約がネックになるか」が場所によって変わるため、厳密解が消えるリスクがあります。

なので、同じリソースに対してMax-Min制約が同居する場合は、ドミナンス出来ず、「同じである」ことだけになってしまう場合が多いと思います。特にScheduling Benchmarksにおいては、Max-Minの幅が異常に狭く、殆どドミナンスが効きません。結果、ラベルの爆発がinstance13程度で生じ、一般的なラベル設定法では、解くことが出来ません。

A dedicated pricing algorithm to solve a large family of nurse scheduling problems with branch-and-price

RowActivityの計算方法

 Σai(xi)≦b[min:max]のとき、row price(dual)は、どちらを指すか？　悩ましいのですが、それは、Row Activityをみて判別するということのようです。LPSolver毎に、この辺の扱いは異なるようで、注意が必要です。LPSolverに依存しない形ならば、bのMIN/MAXを分離して記述すればよいでしょう。

判別は、bを見て、bになっている方が効いている制約になります。

Q.病欠時の設定２

 Ans.前回、病欠時のエラーを安直は方法で回避しましたが、今回は、恒久対策の方法を述べます。

問題の発端は、公休ラベルが以下のように多数、使用されていることにあります。

本来は、「病欠」で休んでいるのですから、公休ではなく、「病欠」というシフトにした方が良いように思います。

これを行うには、有給の別名としています。この有給は、自動シフトがチェックされていないので、予定を入れなければ出現しません。つまり、他の制約で使用されていない可能性が高いと考えられ、余計なエラーが出にくいであろう、という理由です。

しかし、実際に求解してみると以下の制約でエラーとなりました。が、スタッフプロパティシート上、夜勤数と公休数を変更することで対応可能です。

夜勤数を少なくします。

公休数を少なくします。

解が出ました。前回の値より余計なエラーが生じていないことが分かります。

Q.マイクロソフトアカウント名が分からない

Ans.

マイクロソフトアカウント名が分からないと購入履歴が分かりませんし、サブスクを停止することは出来ません。アカウント名が分からない場合は、ググると色々な方法があるようですが、マイクロソフトストアに紐づいているアカウント名であることが必要です。 

今、スケジュールナースを使用出来ているのであれば、必ずマイクロソフトストアに紐づいたマイクソフトアカウント名が存在し、以下の方法で、購入履歴を確認することが出来ます。

スケジュールナースを使用出来ない状態であれば、今から述べる方法は使えません。

１）マイクロソフトストアを出します。

２）サインインのアイコンをクリックすると下のようなダイアログが出現します。

３）サインインをクリックすると、私の場合、複数のアカウントを持っているので、複数のアカウント名が表示されます。表示されているアカウント名のうち、どれかがマイクロソフトストアと紐づいているアカウント名ですが、それがどれかはこの段階では分かりません。

４）なので、1個づつアカウントにサインインして購入履歴を確認していくしかありません。

しばらく、サインインしていない場合は、認証が行われることがあるようです。認証をクリアした前提で話を勧めます。

上のアカウント名をクリックすると、サインインのアイコンが変化します。

アカウントでデバイスの管理をクリックします。注文履歴を見ると、このアカウントでは、サブスクの購入が行われていないことが分かります。３）に戻って次のアカウント名を試します。

このようにして、紐づいたマイクロソフトアカウントが分かります。

紐づいたマイクロソフトアカウントさえ分かれば、サブスクを停止するのは、造作ないことだと思います。

以上です。