HIGHSベンチマーク

 http://plato.asu.edu/ftp/milp.html

にHIGHS1.1.1のMILPベンチマーク結果がUpdateされています。このベンチマークでは、240問題を一定時間内に解きます。解けた問題数が一番下のsolvedで分かります。Gurobiが一番解けていますがこれはいつもの事です。

1threadと８threadが載っています。1threadについて見て見ると、scaledは、Gurobiを1としたときの時間比で、CBCは、８．59倍比ということになります。(Dec.30.2021時点のデータ）体感的に、もう少し差があるような気がするのは、解けた問題を対象にした時間比較だからです。解けない問題を何らかの方法で時間に換算すれば、差はさらに広がるでしょう。

8threadでは、HIGHS1.1.1が追加されており、CBCでは、約14.5倍、HIGHSでは、約13倍になっています。ですから、HIGHSの方が少しだけ良いという私のNSPでの計測結果と符合しているのではないかと思います。

＝>https://schedule-nurse.blogspot.com/2022/02/highs.html

Mittlemanベンチマークについては、以下が参考になります。

untitled (orsj.or.jp)

COPTがMILPに参戦してきてそれなりの結果を残しています。こういう最適化領域の基幹的なソルバを設計する能力は、そのまま国力に通じる部分があると思います。（かってLSIを設計していたとき、その基幹的ツールである合成ツールは、Synopsysのデザインコンパイラという米国製が業界を席巻していました。ネーミングセンスがありますね。）

SCIPのソースコード行数は、GCC並みの50万行だったように記憶しています。ですから、一足飛びに商用並みのソルバを期待するのは難しいでしょう。HIGHSは、CBCに比べれば、モダンな筆致で、かなりコンパクトに書けています。MIPソルバについては、ほぼJulianHall教授とLeona Gottwaldさんの二人で開発しているようです。（Leona Gottwaldさんのプリプロセッサは、SCIPでも使えるようです。少し読んでみたのですが、殆ど理解できませんでした。）ちなみCBCは、IBMにいたJohnForrestさんによる開発で、かなりのご高齢のはずですが、未だメンテされているようで頭が下がります。後継の複数の開発者(大学の先生方)もメンテされているので開発が途絶える心配はないと思います。

日本の商用ソルバとしては、NTTDATAのNuOptが有名です。残念ながらGurobi/Cplexと比較データはありません。

クラッシックベンチマークの評価

 下界が分かるということは、素晴らしいことで、これ以上良い解はないことが解く前から分かります。最適化ソフトは、所詮は、探索をするものなのですが、どこまでやればよいのか、誰かが教えてくれないといつまでも探索を続けることになります。ところが、予めこれ以上良い解はないという値が分かっていれば、その値に到達した時点で探索を止めてよい訳です。（逆にそれを知りえないソルバでは、タイムアウトで止めるかユーザが止めるしかありません。）

クラッシックベンチマーク郡を再度評価していて、実は、このベンチマーク全ての厳密解を出せるソフトはGurobi/Cplexを含めて一つもない、ということに気づきました。

正確には、現在のスケジュールナースは出せますが一度の求解では、出力できませんでした。Algorithm3では、これを改善し、クラッシックベンチマークでは、全ての厳密解を一回の求解ボタンで出せる世界初のソフトとなります。これにより、実務的にも大方厳密解を出せるのではないか？と期待しています。

そこで、厳密解インスタンス率という、性能指標を提唱したいと思います。仮想的に世の中にある全てのベンチマークソフト郡、実務インスタンス郡を全て集めてテストしたときに、上界まで到達出来たインスタンス郡の比率を指します。

例えば、30secでは何％、60/300/600secでは何％　という風にプロットしてみたらどうなるか、興味があります。実際それが、体感的な性能に一番フィットするのではないかと思います。

＝＞評価しました。

https://schedule-nurse.blogspot.com/2022/02/blog-post_16.html

HIGHSのMIPソルバ

 JullianHall教授がCBCよりめっちゃ速くなったぜ！と豪語していたので、少し評価してみました。確かに、CBCより速い場合もありました。小さいインスタンス用途には良いのではないでしょうか？

SchedulingBenchmarksでは、Instance4までは解けましたが、それ以上は厳しそうです。確か、CBCが数分で解けるのは、Instance3位までだったので、多少良くなっているような気もします。=>https://schedule-nurse.blogspot.com/2022/02/highs.html

ちなみに、現在スケジュールナースは、Instance6まで厳密解を数秒、Instance8までの厳密解を数十秒以内に出力でき、Instance15/Instance21/Instance22の世界記録を保持しています。またINRC2(Internatial Nurse Scheduling Competition2 )データでは、State Of Art MIPSソルバを圧倒し、全インスタンスのKnownBestValue(これまでの世界記録)を更新しています。また、Classical　Benchmarksでは、全てのリニア重みインスタンスについて厳密解を出力できる世界初のソルバです。現在、他に出来そうなソルバは見当たらないので唯一無二のソルバになります。

マルチコア時代に性能を出すために

 処理を分割して、単純にマルチスレッドにしただけで性能が向上すれば何も問題ないのですが、大抵の場合ボトルネックがあります。それは、各コアのキャッシュに載るかどうかということです。単純に参照データがコアキャッシュ内に載れば何も問題はありません。その場合は、ほぼCPUコア倍に性能の向上が期待できます。問題は、載り切らない場合どうするか？ということです。その場合は、

１）なんとかして、データ圧縮する

２）シーケンシャルアクセスしかないようにする

の何れかの方法を取る必要があります。シーケンシャルアクセスしかほぼないのならば、数GBのデータであってもキャッシュは効きます。Simplexのマルチコア化が難しいのは、大規模インスタンスになると２）が難しくなるからだと思います。

シングルコア性能が頭打ちの時代ですが、より速く答えを出すというソルバに求められることは変わりません。未来永劫変わらない普遍的な要求だと思います。

Instance22世界記録更新

ようやく満足できる解が見つかったので承認申請しました。 Ryzen８cores　開発中のAlgorithm3で46992secかかりました。Search Spaceが10の18953乗です。最適解証明はできませんでした。

Instance22　LB:30240　UB:30244

Instance22世界記録更新

 UB:31161⇒30441　

に更新しました。未だ途中経過なので承認申請していません。（チューニングしながら行っており更新したらコード修正⇒再トライを行っています。）

AVX2検出

AVX2は、自作の Interior Point Methodを使っています。通常は、Simplexの雄CLPを使うのですが、大規模インスタンスINRC2 n0120w8 や、SchedulingBenchmarks Instance21以上では、Simplexより内点法の方が速度的に有利です。そのために切り替えていますが、万が一AVX2をサポートしないCPUであった場合に落ちてしまいます。通常の実務インスタンスで、この規模はほぼないと言えますが、Githubに上げるプロジェクトを駆動する場合もあるでしょう、そういった対策の意味で、CPUがAVX2をサポートしているかどうかを知る必要がありました。ありがたく、下記を使わせて頂いております。

https://gitlab.com/yoshimoto/cpuid/-/blob/master/cpuid.cpp

Instance22世界記録更新 By Algorithm3

 更新しましたが、未だ途中経過なので承認申請はしていません。

UB:31279⇒３１１６１(Search Spaceがまた前回(Instance21)から上がって、１０の18953乗になっています。）

今回は、Algorithm3によるソルバでの途中経過です。Algroritm3は、Near Optimalなアルゴリズムで、基本的に厳密解を保証しません。厳密解アルゴリズムは、Algorithm4ですが、今までの評価では、Algorithm3がAlgorithm4に精度的に劣るケースは発見されていません。また、Algorithm4では、instance21以上では、実質的にコンパイル不可能ですが、Algorithm3では、(解けるかどうかは別にして)コンパイルは可能です。また、実務的インスタンス、例えば池上ベンチマークもAlgorithm4ではコンパイルできませんが、Algorithm３では問題なくコンパイル可能です。まとめると、

Algorithm1：SAT系ソルバ

Algorithm4 :数理的ソルバ　(コンパイル出来れば)速い　厳密解探索用、コンパイル出来ないことがある。

Algorithm3 :数理的ソルバ　汎用　Near Optimal。  Algorithm1で時間がかかる場合、精度と速度で有利（ソフト制約が多数かつ多数のソフトエラーが残る場合）。また長大規模(3ヶ月以上）または、大規模(100人以上)でも、Algoritm1より有利になります。コンパイル出来ないことはないことを目指している。(しかし、経験的に枯れたAlgorithm1レベルになるには１年以上必要）

CPUコア数が、多くなればなるほど、Algorithm3は有利となります。また、この条件下での学術ベンチマークでは、Gurobi/Cplex、AutoRoster含め他のソルバを圧倒します。

現在、Algorithm3についてベンチマークの評価とチューニング作業中です。

実務インスタンスについては、シフト系については、実装を完了していますが、タスク系については、未だ実装していません。また、ペア制約も現在実装未です。

       

量子アニーリングについて

組み合わせ最適化は、ナーススケジューリングを包括する広範囲な問題領域です。

「量子」と組合せ最適化に関する怪しい言説 ―とある研究者の小言― - むしゃくしゃしてやった，今は反省している日記 (hatenablog.com)

それでは、古典的数理的解法で、ナーススケジューリング問題はどこまで解けているか？ということを少し論じてみたいと思います。

ナーススケジューリングの黎明期は、メタヒューリスティクスによる解法が主で、タブサーチ等が用いられました。

その後、MIPソルバーの発展によって、Gurobi・Cplexを始めとする数理的ソルバは、従来の解を更新、なおかつ、そのうちの超大規模を除く殆どを厳密解として提示出来るようになりました。(INRC1・SchedulingBenchmarks)　

そこで、INRC2では、問題をより大規模にして、なおかつ問題を複雑にしてMIPソルバーでは解きにくい形態としています。実際、INRC2問題は、MIPソルバーでは、殆ど解けていません。（実インスタンス形態としては、インスタンスによるのですが、どちらかというと、INRC2に近い実感があります。）

現在、MIPソルバーで、かなり解けるようにはなったけれども、全てが解ける訳ではありません。また、MIPソルバー間、AutoRoster等のナーススケジューリングソルバ間でも、性能の差がある、というのが現在地になります。

それでは、StateOfArtのソルバで、一体どこまで解けているか？という問いに対する回答が、スケジュールナースⅢになります。

現在、スケジュールナースⅢでの数理的解法結果を一連のベンチマークとしてデータを採取中です。実務問題については、未だ課題が山積していますが、少なくともベンチマークについては、動いており現在公開に向けバージョンアップしたバージョンAlgorithm3としてチューニング準備中です。ちなみにAlgorithm2は、MIPソルバそのもので、10人以下でしたらそこそこ動きますが、あくまで商用でないMIPソルバだとこんなもんです、程度で殆ど実用的ではありません。Algorithm1は、従来通りで変わりません。Algorithm4は、バージョンアップしていますがAlgorithm3の特殊形態です。Algorithm3は、汎用化した数理的ソルバです。

Algorithm3が、ナーススケジューリング問題の古典的解法によるStateOfArtと言い切ってよいと思います（GurobiでもCplexでもなく）。

一つ指摘しておきたいことは、必ずしもMIPソルバが全能ということではなく、これは容易に解けるだろうと思われる小さな問題でも、MIPソルバで解けなかったり、意外に時間がかかる事例が散見されることです。例えば　

Benchmarks | What is Schedule NurseⅢ (nurse-scheduling-software.com)

で、GPost/GPostB,BCDT-Sep,WHPP,Valouxis-1、ikegami-3Shiftxx 等です。これらは、人工的・機械的にベンチマーク用として造られたものではなく、実務問題をモデリングしていることにご注意ください。GPostは、僅か8人ですが、数理的に解くのは難しい部類にはいります。

ベンチマークは、アカデミック上の特定の実装が有利に働くような意図が背景にあり、必ずしも実問題にマッチしていません。実務問題とは基本的に異なりますが、INRC2に関しては、シフト形態は別にしてほどよくハード・ソフト制約がブレンドされ実務用途に近いと思います。

どのようなインスタンスでも安定して、短時間にNear Optimal(Ex.30sec/1min) 、時間をかければ厳密解に到達できることが、ソルバに求められる要件です。

いずれにせよ、今後はスケジュールナースⅢが一つの指標になると言い切ってよいと思います。

CPU使用率計測

 思ったように超大規模でのマルチスレッドの性能が出ないので、CPU使用率をタスクマネージャではなく、ソルバ上で得ようと思いました。中々良いコードが見当たらなかったのですが、StackOverflowにありました。Windows用です。

#pragma once
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include "pdh.h"

#pragma comment(lib, "pdh.lib")

class Query {

    PDH_HQUERY cpuQuery;
    PDH_HCOUNTER cpuTotal;
public:
    Query() {
        PdhOpenQuery(NULL, NULL, &cpuQuery);
        PdhAddCounter(cpuQuery, TEXT("\\Processor(_Total)\\% Processor Time"), NULL, &cpuTotal);
        PdhCollectQueryData(cpuQuery);
    }

    operator double() {
        PDH_FMT_COUNTERVALUE counterVal;

        PdhCollectQueryData(cpuQuery);
        PdhGetFormattedCounterValue(cpuTotal, PDH_FMT_DOUBLE, NULL, &counterVal);
        return counterVal.doubleValue;
    }
};

使い方は、簡単です。omp forループ後に、 

Query q;

cout << q << "[%]" <<endl;

で表示されます。