2025年4月のH. Mittelmann氏の線形計画ソルバーのベンチマーク結果を見ると、いつの間にか”cuPDLP”というソルバーが追加されていました。
気になったので調べてみました。
2.1. 概要
cuPDLPは2023年に発表された、GPUベースの線形計画(LP)ソルバーです。一般的な線形計画ソルバーが単体法や内点法で実装されるのに対し、このcuPDLPはGPUでの並列演算に適した手法として、PDLPという方法を採用しているそうです。PDLPは、Primary-Dual Hybrid Gradient (PDHG) という非平滑凸最適化問題を解くための手法をLPに特化させて効率的に実装したもので、この手法は問題規模(制約条件の非ゼロ要素数)に対して計算時間がほぼ線形にスケールするため、First-order methods (FOMs)とも呼ばれます。
Arxivの論文:
ソースコード:
https://github.com/COPT-Public/cuPDLP-C/tree/main
pythonのAPIも開発されています。
2.2. 性能
| Solver | CLP | COPT | OPTV | MOSEK | HiGHS | GLOP | SPLX | XOPT | CUPDL |
|---|---|---|---|---|---|---|---|---|---|
| Score | 27.2 | 1 | 1.68 | 7.45 | 17.0 | 59.4 | 93.5 | 6.60 | 1.84 |
| Solved | 40 | 65 | 63 | 52 | 51 | 33 | 32 | 52 | 57 |
※上表はMittlemann氏のサイトの数値をそのまま引用。一番右のCUPDLがcuPDLPの結果を表す。
※Scoreは最速のCOPTを1としたときの計算時間比で、小さいほどソルバーの性能が良い。
※Solvedは65インスタンスのベンチマーク問題のうち制限時間以内に解くことができた問題数。
cuPDLPは商用のCardinal Optimizer (COPT), Optverse(OPTV)と比べると少し遅いものの、そのほかのソルバーと比べると圧倒的に高速です。特にフリーのソルバーの中で比較すると、CLPの15倍、HiGHSの9倍高速です。
Google Colaboratoryで無料でGPUが使えるので、試してみました。
3.1. ライブラリインストール
# システムパッケージ更新＆必須ライブラリをインストール
!apt-get update -y
!apt-get install -y \
git cmake build-essential \
libopenblas-dev zlib1g-dev
!apt-get install -y libeigen3-dev
3.2. cuPDLPのクローンとHiGHSのインストール
%%bash
# HTTPS でクローン
git clone https://github.com/COPT-Public/cuPDLP-C.git
cd cuPDLP-C
# ルート直下の .gitmodules を書き換え
sed -i \
-e 's|ssh://git@ssh.github.com:443/pybind/pybind11.git|https://github.com/pybind/pybind11.git|g' \
.gitmodules
# サブモジュール定義を同期
git submodule sync
# HTTPS でサブモジュールを取得
git submodule update --init --recursive
cd ..
# HiGHS のソース取得
git clone https://github.com/ERGO-Code/HiGHS.git highs_src
# ビルド用ディレクトリ作成
mkdir highs_build && cd highs_build
cmake -DCMAKE_BUILD_TYPE=Release \
-DBUILD_SHARED_LIBS=ON \
-DHIGHS_ZLIB=ON \
../highs_src
cmake --build . --target install
3.3. HiGHSのPath設定
import os
# HiGHS のインストールパス
os.environ['HIGHS_HOME'] = '/usr/local'
# Colab の CUDA ランタイムパス（通常 /usr/local/cuda）
os.environ['CUDA_HOME'] = '/usr/local/cuda'
3.4. cuPDLP-Cのビルド
%%bash
cd cuPDLP-C
#rm -rf build
mkdir build && cd build
# GPU と Python バインディングを有効化
cmake \
-DBUILD_CUDA=ON \
-DBUILD_PYTHON=ON \
-DCMAKE_BUILD_TYPE=Release \
-DCMAKE_CXX_FLAGS="-Wno-deprecated-declarations" \
..
cmake --build . --target pycupdlp -j$(nproc)
warning: ‘XXXXXX’ is deprecated的なエラーが大量に出力されますが、無視しました。
3.5. pycupdlp*.soファイルのPathを登録
%%bash
# pycupdlp*.soファイルを探す
find cuPDLP-C/build -type f -name "pycupdlp*.so"
出力例:
cuPDLP-C/build/lib/pycupdlp.cpython-311-x86_64-linux-gnu.so
import sys
# 上で見つけたパスを先頭に追加
sys.path.insert(0, "/content/cuPDLP-C/build/lib")
3.6. Pythonパッケージのインストール
!pip install mip
!pip install pulp
!pip install highspy
ここまでで実行環境のセットアップは完了です。
3.7. ベンチマーク問題のダウンロード
ex10という問題インスタンスを選んだ。Mittleman氏のベンチマークでは、
- CLP: 32秒
- HiGHS: 24秒
- cuPDLP: 1秒
で最適解が得られています。
%%bash
# ベンチマーク用問題をダウンロード
mkdir mps_data
cd mps_data
wget https://miplib2010.zib.de/download/ex10.mps.gz
gzip -d ex10.mps.gz
cd ../
pulpではなぜかmiplibのmpsファイルが正しく読み込めないので、Python-mipを使って読み込めるmps形式に無理やり変換しました。
import mip
model = mip.Model()
model.read("mps_data/ex10.mps")
model.write("mps_data/ex10_mip.mps")
gz形式で保存されるので、解凍します。
%%bash
gzip -d mps_data/ex10_mip.mps.mps.gz
3.8. CLPとHiGHSによる求解
pulpを使って解きました。
import pulp
vars, problem = pulp.LpProblem.fromMPS("./mps_data/ex10_mip.mps.mps")
# HiGHSでの求解 (約70sec)
t0 = time.time()
solver=pulp.HiGHS()
problem.solve()
print(f"Elapsed time for HiGHS: {time.time() - t0}[s]")
# CLPでの求解 (約77sec)
t0 = time.time()
solver=pulp.COIN_CMD()
problem.solve()
print(f"Elapsed time for CLP: {time.time() - t0}[s]")
Colaboratoryではソルバーのログが標準出力されなかったため、求解そのものの時間以外も含む形で時間を計測しました。
3.9. cuPDLPによる求解
MPS形式のファイルを読み込めるので、簡単に計算できました。
# cuPDLPで求解 (約0.7sec)
import pycupdlp
c = pycupdlp.cupdlp()
c.readMPS("mps_data/ex10.mps")
t0=time.time()
c.solve()
print(f"Elapsed time for cuPDLP: {time.time() - t0}[s]")
求解時間は0.7秒と、HiGHSやCLPより100倍ほど高速でした。無料のColaboratoryで選択できるGPUはT4なので、普通に個人で買えるレベルのGPUでも十分高速化が期待できそうです。
まとめ
- cuPDLPはフリーで使える中では最も高速なLPソルバー
- Colaboratoryでmiplibのex10インスタンスを解いたところ、高速に最適解を得られた
- CLP: 77秒
- HiGHS: 70秒
- cuPDLP: 0.7秒
- PythonのAPIもあるので、ある程度実用にも堪える？
疑問点
- 解の精度と求解時間の関係 (PDLPは求解精度の基準が高いほど反復回数が増えやすいらしい)
- 感度分析への応用 (PDLPだと感度分析に必要な情報が得られない？)
- 混合整数線形計画問題への適用(分枝限定法には組み込めない？)
- バグや苦手な問題の傾向はあるか？
Views: 3
