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

# 1. はじめに

2025年4月の[H. Mittelmann氏の線形計画ソルバーのベンチマーク結果](https://plato.asu.edu/ftp/lpopt.html)を見ると、いつの間にか"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版](https://arxiv.org/pdf/2311.12180)
- [C言語版](https://arxiv.org/pdf/2312.14832)

ソースコード:
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が使えるので、試してみました。

https://colab.research.google.com/drive/1JYRHu-OITprFw5oHhOFbVezYWfNO1di7?usp=sharing

## 3.1. ライブラリインストール
```bash
# システムパッケージ更新＆必須ライブラリをインストール
!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
%%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設定
```python
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
%%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
%%bash
# pycupdlp*.soファイルを探す
find cuPDLP-C/build -type f -name "pycupdlp*.so"
```
出力例:
> cuPDLP-C/build/lib/pycupdlp.cpython-311-x86_64-linux-gnu.so

```python
import sys
# 上で見つけたパスを先頭に追加
sys.path.insert(0, "/content/cuPDLP-C/build/lib")
```

## 3.6. Pythonパッケージのインストール

```bash
!pip install mip
!pip install pulp
!pip install highspy
```

ここまでで実行環境のセットアップは完了です。

## 3.7. ベンチマーク問題のダウンロード

ex10という問題インスタンスを選んだ。Mittleman氏のベンチマークでは、
- CLP: 32秒
- HiGHS: 24秒
- cuPDLP: 1秒

で最適解が得られています。

```bash
%%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形式に無理やり変換しました。

```python
import mip
model = mip.Model()
model.read("mps_data/ex10.mps")
model.write("mps_data/ex10_mip.mps")
```
gz形式で保存されるので、解凍します。
```bash
%%bash
gzip -d mps_data/ex10_mip.mps.mps.gz
```

## 3.8. CLPとHiGHSによる求解

pulpを使って解きました。
```python
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だと感度分析に必要な情報が得られない？)
- 混合整数線形計画問題への適用(分枝限定法には組み込めない？)
- バグや苦手な問題の傾向はあるか？