Python数理最適化パッケージPuLPの計算エンジンを速いものにする（Windows版お手軽編） & 計算時間を指定する

2021/09/04 追記

• ここに書かれてることをする必要はありません。これからはPuLPではなく、Python-MIPを使ってください。詳しくは以下の記事をご覧ください。

今度こそ？使い物になるフリーの数理最適化（混合整数最適化）ソルバー Python-MIP

2020/08/26 追記

• 最新版(2.3)では、計算時間を指定する maxSeconds= オプションは timeLimit= オプションに名前が変わったようです。

はじめに

数理最適化問題（数理計画問題）の中で、線型最適化問題（線型計画問題）や整数最適化問題（整数計画問題）（※ただし数式がすべて線型のもの）を解いてくれるPythonパッケージとして、PuLPがあります。

• 参考Qiita記事： Python+PuLPによるタダで仕事に使える数理最適化

PuLPは、解きたい対象をPython上で数式として記述できるモデリングインターフェース部分と、数理最適化ソルバーと呼ばれる、式として記述したものを解いてくれる計算エンジン部分とが、きれいに分かれています。PuLPには、数理最適化ソルバーとして、 無償で商用利用可能な COIN-CBC（ 公式サイト（GitHub） ）の、とあるバージョンが同こんされているほか、自分で入手したほかの数理最適化ソルバーを呼び出すこともできます。ということは、COIN-CBCより高性能な数理最適化ソルバーを用意すれば、より短い計算時間で解くことができるのですが、無償で商用利用可能なソルバーの中でCOIN-CBCより速いものはMIPCLくらいしかなく、そのMIPCLも、2020年5月現在、入手性に謎の部分がでてきました。

• 参考Qiita記事： ついに使い物になるフリーの数理最適化ソルバーが登場？　MIPCL

ところで、整数最適化問題を解くアルゴリズムは、特にその中の分枝限定法と呼ばれる部分などについて、並列処理が可能であり、それにより計算時間をけっこう短縮できます。有償のソルバーやMIPCL、そして公式サイトで配布されているCOIN-CBCは、マルチスレッドで動作するのですが、PuLPに同こんされているCOIN-CBCは、少なくともWindows版については、マルチスレッドで動作しないのです。

そこで、PuLPから呼び出す数理最適化ソルバーを、マルチスレッド対応版のCOIN-CBCに変更することで、計算時間を短縮する方法を紹介します。今回は、速報版として、お手軽にできる方法を扱います。ついでに、計算時間の上限を指定する方法にも触れます。

※ Macの方は、自分でインストールした CBCソルバをPuLPで使用する の記事が参考になると思います。

実験環境

• Windows 10 1909 64bit
  • 管理者権限を持つアカウントで作業
    • （作業中に管理者権限を求められた記憶はなし）
• Python 3.7 64bit (Anaconda3 2020.02 64bit)
  • ユーザー領域にインストール（Anacondaインストール時に「Just Me」を選択）
• PuLP 2.1
• 2020/05/18にmasterブランチからビルドされたCOIN-CBC
• Visual Studio Code 1.45.1
  • ユーザー領域にインストール

ダウンロード

Python+PuLPによるタダで仕事に使える数理最適化 の記事などに従って、PuLPのダウンロードとインストール、軽い動作確認はできているものとします（最適化の計算では、特に指定しない場合、PuLP同こん版のCOIN-CBCが使用されます）。

今回、追加作業として、 https://bintray.com/coin-or/download/Cbc/master#files の Cbc-master-x86_64-w64-mingw32.zip をダウンロードします。ダウンロードしたら、zipファイルなので、展開します。

• このバイナリーは、masterブランチからビルドされたもののようです。上記のサイトの中や COIN-CBCの公式サイト（GitHub） を探していくと、バージョン番号のついたバイナリーも見つかりますが、そちらはライブラリーの依存関係を自分で解決する必要があるようです。
  • masterブランチからビルドされたものは、バージョンが固定された安定版とは限らないので、使用することに不安はありますね…自己責任の度合いがより強くなります。
• Cbc-master-win64-msvc16-mt.zip （Visual Studio 2019でコンパイルしたもの？）などほかのバイナリーは、なぜかマルチスレッドに対応していませんでした。

コード

ダウンロードして展開したCOIN-CBCが、 C:\Users\(ユーザー名)\Desktop\Cbc-master-x86_64-w64-mingw32\bin\cbc.exe にあると想定します。

こちらの記事の例(2) の コード pulp_problem_2.py を取り上げて説明しますと、

pulp_problem_2.py

# （前略）
# 計算
# ソルバー指定
solver = pulp.PULP_CBC_CMD()
# （後略）

の部分を、

pulp_problem_2_mt.py

# ソルバー指定
solver = pulp.COIN_CMD(path=r'C:\Users\(ユーザー名)\Desktop\Cbc-master-x86_64-w64-mingw32\bin\cbc.exe', threads=8, maxSeconds=120.5)

(※ 2020/08/26追記: PuLPの最新版(2.3)では、 maxSeconds= は timeLimit= に名前が変わったようです。)

に変えれば、マルチスレッドで動作します。

• path=(COIN-CBCのバイナリーのパス) で、呼び出すCOIN-CBCのバイナリーのあるところを指定します。
  • 先頭に r のついた文字列は raw文字列 というやつで、Windowsのファイルやフォルダーのパスを指定する際に使うと便利なものです。
• threads=(スレッド数) で、COIN-CBCで使用するスレッド数を指定します。いくつがよいかは、下記のベンチマーク結果が参考になると思います。
• 今回の記事の主題から外れますが、 maxSeconds=(計算時間上限（秒）) で、計算時間の上限を指定できます。
  • 指定時間内に計算が終わる場合もあります。その場合、（最適解が存在するインスタンスであれば）最適解が返ってきて、かつ、その解が最適解であることが計算を通して理論的に保証されています。
    • （インスタンスが非有界（目的関数を無限に小さく（大きく）できる）や実行不可能（制約を満たす解が存在しない）である場合は、そうであることが指定時間内に判明したということになります。）
  • 計算が終わらないまま指定時間に達した場合は、それまでに見つかった中でいちばんよい解が返ってきます。
    • 返ってきた解は、実は最適解であるかもしれないし、そうでないかもしれません。仮に最適解であったとしても、最適解であることは理論的に保証されていません。
    • この「指定時間内で見つかった解を返す」機能の使い道のひとつとして、問題に対して自前で（メタ）ヒューリスティクスのコードを組んで指定時間内でそこそこよい解を探す代わりに、数理最適化ソルバーに投げて同じ時間内で見つかったそこそこよい解を返してもらうことが考えられます。
    • 指定時間内に解が1つも見つからない可能性もあります。その場合、そもそも実行可能解（制約を満たす解）が存在しないのかもしれないし、存在はするものの数理最適化ソルバーが見つけられていないのかもしれません。

ベンチマーク

前の記事 と同じく、グラフクラスタリング（与えられた無向グラフを、いくつかの密な部分グラフに分割する問題）に関する こちらの論文 の定式化を解いてみました。環境はIntel Core i9-9900K（8コア16スレッド）です。
この論文の定式化に基いてインスタンスを解いた印象としては、最適解を見つけるのにも少し時間がかかるものの、それ以上に、見つかった解が最適であることを保証するために多くの時間がかかるようなタイプであるということが挙げられます。

インスタンス	PuLP 2.1付属のCOIN-CBC (1スレ)	2020/05/18版COIN-CBC (1スレ)	2020/05/18版COIN-CBC (8スレ)	2020/05/18版COIN-CBC (16スレ)
1	21.7	22.7	6.9	13.4
2	10.1	11.2	4.3	5.6
3	28.0	20.3	7.2	10.3
4	9.8	19.8	5.4	7.4

（単位：秒）
（おおむね、インスタンスの数字が大きいほど、インスタンスのサイズが大きい）

まず、1スレッドで動作するPuLP 2.1付属のCOIN-CBCのバイナリーと、今回入手したCOIN-CBCのバイナリーを1スレッドで動作させた場合を比較すると、おおむね前者のほうが短時間でインスタンスを解いています。前者のバイナリーは、今回の実験環境の場合、 C:\Users\(ユーザー名)\Anaconda3\Lib\site-packages\pulp\solverdir\cbc\win\64\cbc.exe にあるのですが、これをコンソールから実行させたら、 Version: 2.9.0 Build Date: Feb 12 2015 と表示されました。2020/05/18版は、バージョン2.10.5から2か月ちょっとたったもののようです。数理最適化ソルバーでは、バージョンが上がると、中のチューニングの変更の結果として、かえって解く時間が長くなるインスタンスがでてくることはままあります。
今回入手したCOIN-CBCのバイナリーを、CPUの物理コア数である8スレッドで動作させると、1スレッドのときと比べて、最低でも40%弱の時間でインスタンスが解けました。コア数が1:8なので計算時間が12.5%まで短縮とはいきませんでしたが、なかなかよい結果です。
物理コア数を超えて論理コア数である16スレッドで動作させた場合は、8スレッドで動作させた場合に比べて時間がかかってしまいました。整数最適化は比較的重い処理であることから、SMT機能により別の論理コアとして見えているが物理的には同一のコアの中で、演算器の奪い合いが起こってパフォーマンスが下がったものと推測されます。こういった現象は、例えば行列演算ベンチマークとして知られているLINPACKでも起こります。最近の有償ソルバーだと、自動でCPUのSMT周りの特性をチェックして、スレッド生成数を自動調整してくれるようなのですが、今回入手したCOIN-CBCにはそういった機能はないようなので、自分で明示的にスレッド数 = 物理コア数と設定するのがよいようです。なお、各スレッドの処理をどの論理コアへ割りふるかについては、Windowsの場合はVistaか7のころから、OS側で別々の物理コアにいい感じに割りふってくれているようです。

まとめ

• PuLPにデフォルトでついてくる数理最適化ソルバーは1スレッドでしか動かないので、マルチスレッド動作版をダウンロードし、CPUの物理コア数ぶんのスレッドを指定して呼び出すと、問題を速く解けます。
• PuLPでは計算時間の上限を指定することができます。指定時間内に計算が終わる場合もあります。計算が終わらないまま指定時間に達した場合は、それまでに見つかった中でいちばんよい解が返ってきます。

これからやりたいこと

• マルチスレッド動作版をソースからコンパイルしたい。
• cbc.exe を呼び出すのではなく、（ソールからコンパイルして生成した）DLLを呼び出したい。
  • cbc.exe を呼び出す方式の場合、 PuLPがインスタンスを.mpsと呼ばれる形式のファイルに出力 → cbc.exe が.mpsファイルを読んで計算 → cbc.exe が解を.solと呼ばれる形式のファイルに出力 → PuLPが.solファイルを読み解をセット 、という処理の流れになっているが、規模の大きな問題の場合、ファイルの入出力に時間がかかる。
  • PuLPにはデフォルトで CoinMP.dll が付属しているが、32bit版であり、64bit環境では動かない模様？
• Google OR-Tools に付属しているCOIN-CBCはマルチスレッドで動作するのか否かを調査したい。
  • [2020/06/05追記] OR-ToolsのWindows版のPython版の7.6.7691を試しましたが、マルチスレッドで動作しませんでした。以下のGitHubのIssuesを読むと、Windows版だけ？マルチスレッド非対応のようです。対策方法ですが、マルチスレッド版CBCを手に入れ、Makefileを編集してビルドすればよいそうです。
    • https://github.com/google/or-tools/issues/1656
    • https://github.com/google/or-tools/issues/1805