はじめに
Julia + JuMP + HiGHSを使って、看護師の勤務表を自動生成する最適化プログラムを開発しています。
今回使用するモデルは Mixed Integer Programming（MIP：混合整数計画問題）で、概ね以下の規模です。
変数数 : 約12,000～13,000
制約数 : 約45,000～47,000
binary変数 : 約7,000～8,000
勤務希望、夜勤・日勤人数、連続勤務、スタッフごとの勤務回数、休日配置など、多数の制約を組み込んでいます。
これまで HiGHS 1.12.0 を使用していましたが、HiGHS 1.15 で parallel MIP solver が導入されたこともあり、HiGHS 1.15.1 へ更新して性能を比較してみました。
今回の実測では、
- HiGHS 1.12.0 → 1.15.1 の更新だけでも大幅に高速化した
-
parallel = "on"にすると、探索の重いケースではさらに高速化した - CPUのスレッド数をすべて使えば最速になるわけではなかった
- スレッド数を変えると、実行時間だけでなく探索するNode数やLP iteration数も大きく変化した
という興味深い結果になりました。
実行環境
今回使用した環境です。
OS : Windows 11
CPU : Intel Core i5-10400
6 cores / 12 threads
Memory : 32 GB DDR4
Julia : 1.12.5
JuMP : 1.30系
HiGHS : 1.12.0 → 1.15.1
実行環境 : Docker / Linux
HiGHS 1.12.0から1.15.1へ更新
この比較的重いデータでは、HiGHS 1.12.0使用時のソルバー処理時間の合計は約903秒でした。
HiGHS 1.12.0
約903秒
≒ 15分
HiGHS 1.15.1へ更新すると、Parallel MIPを有効にしていない状態でも約329秒まで短縮されました。
HiGHS 1.12.0 : 約903秒
HiGHS 1.15.1 : 約329秒
約2.7倍の高速化です。
CPU、メモリ、モデルなどは変更していません。
ソルバーのバージョンを変更しただけです。
Parallel MIPを使わなくても速くなっている
当初は、
HiGHS 1.15ではParallel MIPが追加されたから速くなったのでは？
と思いました。
しかし、軽いデータではBranch-and-Boundの探索Node数が、
Nodes : 1
で終了するケースもあります。
これはBranch-and-Bound treeがほとんど展開されず、並列で複数のNodeを探索する余地がほぼないケースです。
それでもHiGHS 1.12.0から1.15.1へ更新すると、計算時間が大きく短縮されました。
さらにLP iteration数も、
47,531
↓
17,465
まで減少しました。
このことから、今回の高速化はParallel MIPだけによるものではなく、HiGHS 1.15.1までに行われたMIP処理の改善も大きく効いていると考えられます。
HiGHS 1.15のParallel MIP
HiGHS 1.15では、parallel MIP solverが導入されています。
HiGHSの公式リリースノートでも、v1.15の主要な変更点としてparallel MIP solverの最初のバージョンが挙げられています。
JuMPから有効にする場合は、以下のように設定できます。
set_optimizer_attribute(model, "parallel", "on")
set_optimizer_attribute(model, "threads", 4)
例えば threads = 4 とした場合、実行ログには次のように表示されました。
Thread count 4 (of 12 threads). Using 7 max workers. Parallel search on
Parallel search on と表示されているので、Parallel MIPが有効になっていることが確認できます。
HiGHS公式ドキュメントでは、parallel = "on" の場合、MIP solverがBranch-and-Bound treeを複数threadで探索すると説明されています。
Parallel MIPはどの程度速くなったか
比較的重いケースでは、HiGHS 1.15.1でParallel MIPを無効にした状態と、有効にした状態で明確な差が出ました。
一例では、
Parallel off : 約168秒
Parallel on : 約125秒
となり、約25%短縮されました。
さらに別の重いケースでは、
Parallel off : 約222秒
Parallel on : 約132秒
まで短縮されました。
こちらは約40%の短縮です。
Parallel MIPは、Branch-and-Bound treeがある程度大きく展開される問題ほど効果が期待できそうです。
一方、Nodes = 1 で終了するような軽いケースでは、Parallel MIPをONにしてもほとんど差がありませんでした。
スレッド数を増やせば速くなるわけではなかった
今回特に興味深かったのが、スレッド数による違いです。
使用しているCore i5-10400は、
6 cores / 12 threads
です。
そのため単純に考えると、
threads = 12
にすれば最も速くなりそうです。
しかし実際にはそうなりませんでした。
ある同一データで測定した結果です。
| threads | 求解時間 |
|---|---|
| 1 | 170.18 sec |
| 2 | 121.09 sec |
| 4 | 126.17 sec |
| 6 | 125.18 sec |
| 12 | 145.44 sec |
このケースでは、最速は12 threadsではなく2 threadsでした。
1 threadから2 threadsへ増やすことで大幅に高速化していますが、それ以上増やしても速くならず、12 threadsでは逆にかなり遅くなりました。
スレッド数によって探索量そのものが変わった
ログを比較すると、その理由の一端が見えてきます。
同じデータについて、Node数とLP iteration数を比較しました。
| threads | Nodes | LP iterations |
|---|---|---|
| 1 | 199 | 457,058 |
| 2 | 122 | 380,390 |
| 4 | 165 | 525,595 |
| 6 | 180 | 640,548 |
| 12 | 194 | 860,043 |
スレッドを増やしたことで、
同じ計算を複数CPUで分担している
だけではないことが分かります。
今回の実測では、スレッド数によってBranch-and-Boundの探索経路そのものが変化しました。
その結果、
スレッド数を増やす
↓
探索するNodeや順序が変化
↓
LPを解く回数も変化
↓
総計算量そのものが変化
という現象が発生しています。
特に12 threadsでは、
LP iterations : 860,043
となり、2 threadsの
LP iterations : 380,390
の2倍以上のLP iterationが必要になりました。
複数CPUで同時に処理できても、処理する仕事そのものが大幅に増えれば、結果として遅くなることがあります。
すべてのケースで2 threadsが最速ではない
ただし、
HiGHSでは2 threadsが最速
という意味ではありません。
別の重いデータでは、以下の結果になりました。
| threads | ソルバー処理時間の合計 |
|---|---|
| 2 | 約270 sec |
| 4 | 約262 sec |
| 6 | 約272 sec |
| 12 | 約273 sec |
このケースでは4 threadsが最速でした。
したがって今回の環境では、
2～4 threads
付近が有力そうですが、最適な値は問題によって変わります。
threads はCPUの論理スレッド数に合わせればよい、とは単純には言えなさそうです。
CPUを交換する前にソルバーの更新が効いた
今回HiGHSを更新する前は、計算時間を短縮するためにCPUの交換も検討していました。
しかし実際には、CPUを変更せずHiGHSを更新しただけで、重いケースのソルバー処理時間が、
約903秒
↓
約329秒
まで短縮されました。
さらにParallel MIPを利用することで、
約262～273秒
程度まで短縮できるケースもありました。
約15分かかっていた計算が、4～5分程度になったことになります。
今回のケースでは、CPUを買い替えるより先にソルバーを更新した方が、はるかに大きな性能改善が得られました。
最適化ソフトウェアでは、ハードウェア性能だけでなく、ソルバー側のアルゴリズム改善も非常に大きな影響を持つことを実感しました。
ベンチマークについての注意
今回掲載している数値は、私が実際に使用している看護師勤務表モデルで測定したものです。
MIPでは、
- モデルの構造
- 制約
- 目的関数
- 初期解
- CPU
- HiGHSのバージョン
- スレッド数
などによって結果が大きく変わります。
またParallel MIPでは、スレッド数によって探索経路自体が変化するため、単純なCPUベンチマークのように綺麗な倍率にはなりません。
今回の結果は、
HiGHS 1.15.1なら必ず○倍速くなる
あるいは、
2 threadsにすれば必ず最速になる
という意味ではありません。
あくまで一つの実運用MIPモデルでの実測結果です。
まとめ
今回の検証では、以下の結果になりました。
- HiGHS 1.12.0から1.15.1への更新だけで大幅に高速化した
- Branch-and-Bound treeがほとんど展開されないケースでも高速化した
- HiGHS 1.15のParallel MIPは、探索の重いケースでさらに効果があった
-
threadsは多ければ多いほど速いわけではなかった - 6C/12TのCPUでも2～4 threadsが最速になるケースがあった
- スレッド数によってNode数やLP iteration数そのものが変化した
- MIPでは並列度だけでなく「どのような探索経路を通ったか」も実行時間に大きく影響する
- CPU交換前にソルバーを更新するだけで、大きな高速化が得られる場合がある
HiGHSでMIPを解いていて、しばらくバージョンを更新していない場合は、新しいバージョンで再度ベンチマークしてみる価値があると思います。