はじめに
複数パターンの勤務希望を与え、非商用で使用できるモデラーとソルバーの実行時間を比較しました。目的は看護師のシフト表作成で使う際に「どの組合せが安定して速いか」を示すことです。
Pythonで病棟シフト最適化で作成したコードをベースにしています。
Pythonに加え、数理最適化を行うためモデリング言語JuMP（Julia）の検証も行います。
実行環境
ローカル
- Intel Core i5-10400 @ 2.90GHz
- メモリ 16GB
- Python 3.11.11
- Julia 1.115
Google Golab
- Intel Xeon CPU @ 2.20GHz
- メモリ 13GB
- Python 3.12.11
モデラー
| パッケージ | バージョン |
|---|---|
| PuLP | 3.3.0 |
| mip | 1.16rc1.dev2 |
| PySCIPOpt | 5.6.0 |
ソルバー
| パッケージ | バージョン |
|---|---|
| CBC | 2.10.3 |
| highspy | 1.10.0 |
| SCIP | 9.0.1 |
実行結果（ローカル）
4つの異なる勤務希望パターン（勤務希望1～4）に対して、各モデラーとソルバーの組み合わせで実行時間を測定しました。各組み合わせについて5回の測定を行い、平均値を出しています。タイムアウトは500秒に設定しました。
| モデラー | ソルバー | 勤務希望1 (秒) | 勤務希望2 (秒) | 勤務希望3 (秒) | 勤務希望4 (秒) |
|---|---|---|---|---|---|
| Python-MIP | HiGHS | 20.7 | 40.0 | 24.1 | 30.5 |
| PuLP | HiGHS | 21.5 | 22.2 | 44.5 | 40.7 |
| JuMP(Julia) | HiGHS | 19.8 | 24.2 | 17.9 | 31.9 |
| Python-MIP | CBC | 70.5 | 113.0 | 110.3 | 63.3 |
| PuLP | CBC | 100.4 | 168.1 | 269.2 | 122.7 |
| PuLP | SCIP | 118.9 | >500 | >500 | >500 |
| PySCIPOpt | SCIP | >500 | >500 | >500 | >500 |
実行結果（Google Colab）
| モデラー | ソルバー | 勤務希望1 (秒) | 勤務希望2 (秒) | 勤務希望3 (秒) | 勤務希望4 (秒) |
|---|---|---|---|---|---|
| Python-MIP | HiGHS | 36.1 | 69.0 | 45.4 | 61.5 |
| Python-MIP | CBC | 116.0 | 183.4 | 199.8 | 104.2 |
| PuLP | CBC | 156.4 | 258.4 | 498.0 | 199.2 |
考察
ソルバーによる差異
- HiGHS：すべてのケースで最も高速なソルバーでした。PuLP、Python-MIP、Juliaのいずれのモデラーと組み合わせても優れたパフォーマンスを示しました。
- CBC：HiGHSと比較すると2～5倍程度の実行時間がかかりました。
- SCIP：今回のケースでは最も遅く、勤務希望1を除き、ほとんどのケースでタイムアウトしました。
モデラーによる差異
- JuMP(Julia)：HiGHSソルバーと組み合わせた場合、多くのケースで最も高速なパフォーマンスを示しました。特に勤務希望3では平均17.9秒と圧倒的な速さでした。
- Python-MIP：PuLPと比較して、同じソルバー（CBCやHiGHS）では常に高速でした。勤務希望4でも安定した性能を発揮しています。
- PuLP：HiGHSとの組み合わせでは勤務希望2で好成績（22.2秒）でしたが、他のケースではPython-MIPやJuMP(Julia)より遅い傾向がありました。
- PySCIPOpt：SCIPソルバーとの組み合わせでは、すべてのケースでタイムアウトしました。
環境による差異
- Google Colab環境での実行時間は、ローカル環境と比較して約1.5～2倍長くなる傾向が見られました。これはマシンスペックによるものと考えられます
結論
- 今回のケースに限って言えば、看護師のシフト表作成ではHiGHSソルバーが最も効率的な選択肢であると考えられます。
- モデラーはJuMP(Julia)が最も安定して高速であり、Python-MIPも優れたパフォーマンスを示しました。
- 問題の構造と複雑さによって最適なモデラーとソルバーの組み合わせが変わる可能性があります。
- SCIPソルバーは今回のNSP問題では適していませんでした。特にPySCIPOptとの組み合わせではすべてのケースでタイムアウトしました。
これらの結果は特定のNSP問題インスタンスに基づいており、異なる問題特性や規模では結果が変わる可能性があります。最適な選択は、具体的な問題設定と要件に依存します。
最適化問題を効率的に解くためには、適切なモデラーとソルバーの選択が重要です。この記事が皆さんの参考になれば幸いです。