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でチェックを怠ると余計な仕事を増やすてしまう事例でした。
この間の地震で、仙台は、震度6弱でした。
スマホが被害を受けて買い換えたのですが、AWSにログインできませんでした。
次の手順でも電話はかかってきません。
https://qiita.com/ryouzi/items/3efbf66967a8a1b817ec
どうも
https://ascii.jp/elem/000/002/002/2002627/
ということのようで、何度も行った結果アカウントロックされたようです。サポートの電話をお願いして、無事解除することができました。
今度は、学習して、
https://qiita.com/Catetin0310/items/b91ea87f0ac8ea2f6b2b
スマホを換えても大丈夫なようにしました。
SDKキットで提供していたツール郡の一部がお客さま環境で動作しないとのご指摘がありました。
Staticコンパイルしていたつもりがそうなっていなくて一部共用ファイルを呼び出していたのが原因のようでした。私の環境は、Ubuntu20.04、お客さま環境は、Amazon Linux2です。
Staticコンパイルをトライしたのですが、上手く行かなかったので仕方なく、お客さま開発環境であるAmazon Linux2 環境下でコンパイルすることにしたバイナリを提供することにしました。以下、DockerによるAmazon Linux2環境構築、コンパイルのログです。
sudo service docker start docker run -it amazonlinux:latest /bin/bash cd home mkdir sugatak yum -y install make yum -y install git yum -y install gcc-c++ yum -y install nano yum -y install zip yum -y install clang yum -y install libcurl-devel yum -y install cmake3 cd sugatak git clone https://github.com/awslabs/aws-lambda-cpp.git cd aws-lambda-cpp mkdir build cd build cmake3 .. -DCMAKE_BUILD_TYPE=Release -DBUILD_SHARED_LIBS=OFF make install yum -y install wget yum -y install tar Download Zlib by using the following command : wget http://www.zlib.net/zlib-1.2.11.tar.gz Extract the file from the downloaded package: tar -xvzf zlib-1.2.11.tar.gz Enter the directory where the package is extracted: cd zlib-1.2.11 Now configure Zlib directory: ./configure sudo make install yum -y install openssl cd .. aws-sdk-cpp: git clone https://github.com/aws/aws-sdk-cpp.git cd aws-sdk-cpp mkdir build cd build yum -y install openssl-devel cmake3 .. -DBUILD_ONLY=dynamodb -DBUILD_SHARED_LIBS=OFF -DENABLE_UNITY_BUILD=ON -DCMAKE_BUILD_TYPE=Release make install cmake3 .. -DBUILD_ONLY=lambda -DBUILD_SHARED_LIBS=OFF -DENABLE_UNITY_BUILD=ON -DCMAKE_BUILD_TYPE=Release make install cd .. cd .. yum -y install unzip curl "https://awscli.amazonaws.com/awscli-exe-linux-x86_64.zip" -o "awscliv2.zip" unzip awscliv2.zip ./aws/install bash-4.2# aws configure AWS Access Key ID [****************xxx]: xxx AWS Secret Access Key [****************xxx]: xxx Default region name [xxx]: xxx Default output format [None]: another terminal: docker ps docker export 569> amazon.tar sugatak上で curl "https://nurse-scheduling-software.com/sc3_engine/dec172020/linux/Projects.zip" -o "Projects.zip" unzip Projects.zip docker export 569> amazon2.tar send_to_api_server/build/ cmake3 .. make ./send_to_api_server us-east-1 SC_NURSE_TABLE nobody problem.json ldd send_to_api_server docker export 569> amazon3.tar docker cp 09a735dae425:/tmp/greeting.txt . curl "https://nurse-scheduling-software.com/sc3_engine/dec172020/linux/Projects/schedule_nurse_ver3/send_to_API_server/send_to_api_server" -o "send_to_api_server"
さっぱり表示されないな、単価が低いのかな？と思っていたのですが審査で落ちていました。
よく見ると、AWSとか、Solverと言う単語は、商標にひっかかるのでNGとのことでした。AWSは、ともかく、Solverも商標というのは..
しかたなく、AWSをLambda、SolverをEngineに言い換えて再提出しました。
各人のスケジュールをRosterと言いますが、Rosteringパターンが決まったとき、2回目以降の求解においてさらに高速に解を出したいと思います。そのための調査です。
Branch &Boundの機械学習化
数理的最適化を行うとBranchTreeは避けて通れません。
巡回セールスマンのQiita記事をみていて面白そうだな、と思いました。
Furukawa Laboratory (kyutech.ac.jp)
MIPソルバーの結果を使って学習するようです。
https://arxiv.org/pdf/1907.02206.pdf
ありました。
For example, if your first optimal solution has binary variables with values x1=1, x2=0, x3=1, then you can add the constraint
(1−x1)+x2+(1−x3)≥1
to eliminate the solution x1=1, x2=0, x3=1.
なるほど、上記制約を追加して行けばよいですね。SAT的に、!(x1~x2x3)=~x1+x2+~x3節を加えるのと同じ具合です。
現在、ベンチマークテストでしか、その存在意義を見出せないのですが、これを一般化するべく、改善を再トライしたいと思います。（今までに何度かトライしたものの、大方失敗に終わっています。）アイデアはあって現在Feasibility Study中です。着想は、INRC1インスタンスを解いていて得ました。このインスタンス郡は、実務的には実用度0なのですが、色々と改善のネタを提供してくれて、取り組んで本当によかったです。
上手くいけば実務場面で普通に使えるようになる、あるいは、機械学習化して、さらに速度を上げる等の新たな展開が見えてくるかもしれません。
大規模でSimplexベースだと、途端に求解時間が長くなります。SchedulingBenchmarksのInstance21以上が実質的に解けない主因になっています。Strandmark さんのようにFirst Orderを使う手法がありますが、Algorithm4では、厳密解にこだわっていて、Simplexでもない、First OrderでもないとなるとBarrior Solverに期待をかけるしかないということです。
SCIP品野先生が書かれた
http://www.orsj.or.jp/archive2/or64-4/or64_4_238.pdf
が参考になります。Julian Hall教授のHighsは、以前評価しましたが、Performance的に今ひとつという感じでしたので、もう少しないか探してみました。（Coptも期待したほどではありませんでした。既報）
http://plato.asu.edu/bench.html
こちら、Barrior Solverのなかで、Tulipという新しいソルバを見つけました。Juliaで書かれています。下記がPaperです。（関係ないのですが、上記LPソルバ中、MindOptにしてしろCoptにしろ中国系企業だと思います。LP Solverは、最適化のみならず、機械学習においても基幹技術だと思いますが、日本系が入っていないのは残念なことです。最適化界隈でなにをするにしても、LP Solverを避けて通れないので、いじっているかいないかで、上位アプリにも影響を及ぼすと考えます。この辺、かってLSIの合成ツールでも同じように日本企業は、入っていけませんでした。LSI設計において、合成ツールの世話にならない設計はない訳で、似たような差を感じてしまいます。）
https://arxiv.org/abs/2006.08814
商用ソルバーとの差は、かなりありそうですが、インスタンスによっては、凌ぐ場合もあるということで、見てみようかなと思います。
INRC1の結果についても、見て行きます。
Benchmarks | What is Schedule NurseⅢ (nurse-scheduling-software.com)
sprint 10秒、medium 10分、long 10時間の制限時間です。比較は、厳密解判定までの時間です。sprint_early,medium_early,long_earlyというような、early系では、Gurobi/Cplexが圧倒しています。しかし、late/hidden系になると、途端に求解時間がかかるインスタンスが増え、特にmedium以降のhidden系では、スケジュールナースⅢが圧倒するという結果となりました。early系との違いが何かは、把握していませんが、行制約の何かが影響していると考えています。小規模インスタンス（１０人以下）では、MIPソルバーで厳密解が求められ速い、しかし、中規模・大規模で、厳密解を求めることが難しくなってくると、スケジュールナースⅢの方が勝ってくる、というような全体傾向ではないかと思います。INRC2では、さらに難しいインスタンスとなっており、この傾向を裏付ける結果となっています。
なお、MIPソルバーへのモデリングの影響はあり、モデリングでMIPソルバーの求解速度が変わってきます。たとえば、Santosさんの論文参照。ここでのモデリングは、ScheduleNurseが内部で、認識している問題構造をそのまま、LP/MPS化したということですのでご留意ください。
以上全体の結果について、見ていきました。
Gurobi/Cplexとの比較を行っています。
で、結果を見ると、 殆どのインスタンスで厳密解が求まっていて、しかも、Gurobi/Cplexと比較しても速い傾向にあることが分かります。
Benchmarks | What is Schedule NurseⅢ (nurse-scheduling-software.com)
データ取得中に、ふと見ると、新解が出ていました。これでまた世界記録更新の申請を行いたいと思います。解のValidationは、AutoRosterで行いました。解を読み込ませると、右下に
feasible 3832というのが読み取れます。これは、Instance15のそれまでのUB値3833を更新しています。よって、世界記録ということになります。
これまで、狙っても中々得られなかったのが、アルゴリズムの改善により、期せずして難なく得られました。
古典的なベンチマークについてまとめました。INRC1/INRC2と異なるのは、プログラムでは、なく、人が作った勤務表、という事です。この結果を眺めて思うのは、現在においてもMIPS Solverは、全てにおいて有効という訳ではない、ということです。
Benchmarks | What is Schedule NurseⅢ (nurse-scheduling-software.com)
Algorithm4を改善しました。Algorithm4は、数理的ソルバーで、内部ではとても複雑な処理を行っています。一つの技術ではなく、複数の技術の集積によってこれを達成しています。
一つ一つの要素としては、RCSP(Resource Constraint Short Path Problem)であったりグラフ圧縮(Graph Compression)であったり、Branch&BoundだったりHeuristicsであったり、マルチスレッドだったり・・様々な技術の集積で、ここに至るまで2年を要しました。
が、汎用的とは言い難く、現在のところベンチマーク用途に限定されています。これを汎用的に使えるようにすることが課題として残っています。
前回に比べて、厳密解を得られたインスタンスが多く約半数のインスタンスで、厳密解が求まっています。INRC2は、とても難しい問題で、さすがのGurobiでも厳密解は、一つも求まっていません。(NEOS 8時間タイムアウト）が、多分正しい結果で勿論世界初の成果です。MPS/LPファイルとともにプロジェクトファイル郡をGithubに上げておきます。
