はじめに

複数パターンの勤務希望を与え、非商用で使用できるモデラーとソルバーの実行時間を比較しました。目的は看護師のシフト表作成で使う際に「どの組合せが安定して速いか」を示すことです。
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問題インスタンスに基づいており、異なる問題特性や規模では結果が変わる可能性があります。最適な選択は、具体的な問題設定と要件に依存します。

最適化問題を効率的に解くためには、適切なモデラーとソルバーの選択が重要です。この記事が皆さんの参考になれば幸いです。