はじめに

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にすれば必ず最速になる