フリーで最速のLPソルバー「cuPDLP」を試す

1. はじめに

2025年4月のH. Mittelmann氏の線形計画ソルバーのベンチマーク結果を見ると、いつの間にか"cuPDLP"というソルバーが追加されていました。

気になったので調べてみました。

2. cuPDLPとは

2.1. 概要

cuPDLPは2023年に発表された、GPUベースの線形計画(LP)ソルバーです。一般的な線形計画ソルバーが単体法や内点法で実装されるのに対し、このcuPDLPはGPUでの並列演算に適した手法として、PDLPという方法を採用しているそうです。PDLPは、Primary-Dual Hybrid Gradient (PDHG) という非平滑凸最適化問題を解くための手法をLPに特化させて効率的に実装したもので、この手法は問題規模(制約条件の非ゼロ要素数)に対して計算時間がほぼ線形にスケールするため、First-order methods (FOMs)とも呼ばれます。

Arxivの論文:

• Julia版
• C言語版

ソースコード:
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倍高速です。

3. 試してみた

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://[e-mail]: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でも十分高速化が期待できそうです。

4. まとめと疑問点

まとめ

• cuPDLPはフリーで使える中では最も高速なLPソルバー
• Colaboratoryでmiplibのex10インスタンスを解いたところ、高速に最適解を得られた
  • CLP: 77秒
  • HiGHS: 70秒
  • cuPDLP: 0.7秒
• PythonのAPIもあるので、ある程度実用にも堪える？

疑問点

• 解の精度と求解時間の関係 (PDLPは求解精度の基準が高いほど反復回数が増えやすいらしい)
• 感度分析への応用 (PDLPだと感度分析に必要な情報が得られない？)
• 混合整数線形計画問題への適用(分枝限定法には組み込めない？)
• バグや苦手な問題の傾向はあるか？