制約付最短経路問題は、考えてみるとMIP問題形式そのものなので、NP困難であり問題規模が大きくなると探索空間が爆発し求解が困難となるのは避けられません。ただし、方策が良ければ、そうなる規模は、遅延させることが出来ます。色々なアイデアを試したましたが、大規模で厳密解を得るのは、本当に難しいことです。
が、ようやく先が見えました。多分 長年研究してきたナーススケジューリングの本質、問題の性質が見えたと思います。今までの知見を総動員して、目指していた方式とは異なる解に辿り着きました。この結果は、自分でも意外で、予想していなかった結果です。
Algorithm4として成果が出るのは、もう少し先ですが、主要な問題は解決しました。
c++ - Which is faster: STL queue or STL stack? - Stack Overflow
vectorで実装した方が速そうなのですが、何か理由があるのでしょうか？ という疑問に対して、スタックは可変サイズ用に適するのでdeque ということのようです。
私の用途は、ほぼ、Constant Array Sizeなので、vectorを使えば、Maxまで行った後、reallocateすることはないはずです。よって、次のように実装しました。
std::stack<T, std::vector<T>> Stack;
https://ja.wikipedia.org/wiki/A*
が詳しいです。推定値があるときのダイカクストラアルゴリズムの一般形で、これより速いアルゴリズムは知られていないと思います。問題は、これに制約が加わったRCSPP(Resource Constraint Shortest Path Problem)であり、NP完全な問題になることが知られています。前述のアイデアは、このA*アルゴリズムの一種です。このベンチマークについては、よく知らないのですが、とりあえず、まとまった後の話ですが、NSP問題中に現れる問題をMPS形式にして、MIPソルバーとの比較で速度比較してみたいと思います。
多分、現在でも、コンパイル可能なものについては、スケジュールナースのそれが、Gurobi/Cplexよりも速く最速な筈です。コンパイルが出来ていないものも、前述したアイデアにより、コンパイル可能となり、やはり最速になる予定です。これは、問題構造を良く分かっているからで、一般的に強い解法と、局所的に強い解法の違いであります。
で、バイト？のシフト問題をやっているのを見ました。シフト問題は、意外にメジャーだったのですね。TV CMを打てば、うん千万はくだらないと思うのですが、それでPayする市場規模があるということでしょうか？ だとすると、solutionとしてのソルバーの需要は、意外に大きいのかもしれません。
solutionとしては、王道のMIPソルバー、OptPlanner等のメタヒューリスティクス、自社による開発があるかと思いますが、既に、クラウドベースの、シフト・タスクソルバーが、あります。コマーシャルでした。
は、Algorithm4の中で主要な問題です。SchedulingBenchmarksのInstance13とInstance21以上で解けない、あるいは、実務問題で解けない原因は、このSUB問題が解けないことに起因しています。たとえば、
https://ci.nii.ac.jp/naid/110002812520
は、Boostでも実装されているパレート解法の一種ですが、上記問題を解こうとすると途端にメモリが破綻するのは同じです。
Boost Graph Library: Resource-Constrained Shortest Paths - 1.40.0
実務問題の多くは、上記と同様に基数制約を多く含むこと、シフト数が多いことにより、厳密解を得ようとすると多くの実務問題で破綻します。結果Al4は使えません。
あるアイデアを思いついて試していたのですが、良いところまでは、行くのですが、厳密解を得ようとすると長大な時間がかかる場合があることが判明しました。厳密解をベースを諦め、Heuristicsの一解法ベースとして構築してもよいのですが、もう少しだけトライしてみることにしました。今までやってきた知見をフルに生かせば、多分解決できるだろうという着想を得ました。これを解決して、初めてAl4が実務問題へ投入可能になります。
https://www.jstage.jst.go.jp/article/sicejl/56/12/56_967/_pdf
It looks like you've misspelled the word "Artifical" on your website. I thought you would like to know :). Silly mistakes can ruin your site's credibility. I've used a tool called SpellScan.com in the past to keep mistakes off of my website.
確かに、そうなのですが、同じ文面で、一杯検索で出て来るので、宣伝なのでしょう。
それはともかくGrammarlyでチェックを怠ると余計な仕事を増やすてしまう事例でした。
