Python(pulp) による数理最適化の環境構築は多分これが一番早いと思います

この記事では、Python で数理最適化を行うためのライブラリ `pulp` の導入方法を、できるだけ簡単に説明します。Python 初心者や数理最適化の導入を検討している方を対象としています。

本記事では、Python のパッケージマネージャとして `uv` を使用します。採用理由は以下のとおりです：

- 実行された手順によって手元の Python 環境が破壊されるのを防ぐ
- `uv` は従来ツールよりコマンドが直感的であり、初心者にも扱いやすい
- Python の最新仕様を活用し、高速かつ堅牢な仮想環境を提供する

さらに、デフォルトで使用可能なソルバ `PULP_CBC_CMD` に加え、無償かつ商用利用可能なソルバ `HiGHS` の導入手順も記載します。

## uv のインストール

https://docs.astral.sh/uv/getting-started/installation/ に従って、 `uv` をマシンに導入します。OS は Linux、shell は bash を使用している場合は、以下のようなコマンドとなります：

```sh
curl -LsSf https://astral.sh/uv/install.sh | sh
echo 'eval "$(uv generate-shell-completion bash)"' >> ~/.bashrc
source ~/.bashrc
```

この手順により、 `uv` コマンドにより Python パッケージの管理ができるようになりました。

## プロジェクトの環境作成

`uv init` コマンドにより、 `pulp-starter` プロジェクトを新規に作成します。

```sh
uv init pulp-starter
cd pulp-starter
ls -1
```

以下のように３つのファイルが作成されているはずです;

```sh
README.md
hello.py
pyproject.toml
```

これにより `uv` により管理された Python プロジェクトが作成されたことになります。

試しに以下のコマンドにより Python が動作することを確認しましょう！

```sh
uv run python hello.py
```

問題なく環境構築ができていれば、以下のような出力がされているはずです。

```sh
Hello from pulp-starter!
```

## ライブラリの追加

`uv`の基本的なコマンドを使用して、数理最適化問題を定式化するためのライブラリ `pulp` を導入します。

```sh
uv add pulp
```

### 利用可能なソルバの確認

コマンド `uv run python` を実行することで、仮想環境の Python が起動されます。

```sh
uv run python
```

もしくは、仮想環境をアクティベートすることで `python` コマンドを実行することでも可能です。

```sh
. .venv/bin/activate
python
```

```sh
Python 3.13.1 (main, Dec 19 2024, 14:32:25) [Clang 18.1.8 ] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> 
```

使用可能なソルバをリストアップすると、デフォルトで使用可能な `PULP_CBC_CMD` が実行可能であることがわかります。

```py
import pulp as pl
solver_list = pl.listSolvers(onlyAvailable=True)
print(solver_list)
['PULP_CBC_CMD']
```

なお、本記事における上記のような Python スクリプトは、 `hoge.py` などと名前を付けて保存したうえで

```sh
uv run python hoge.py
```

と実行してもいいし、 `uv run python` のより起動された対話モードの中で行っても構いません。

## 数理最適化の実行

以下の線形計画問題を解きます; 

$$
\begin{align}
& \mathrm{maximize } \ x+y \\\\
& \mathrm{subject \ to } \ \begin{cases} x+2y \le 4 \\\\ 4x + y \le 8\end{cases}
\end{align}
$$

pulp に解かせる際のコードサンプルは以下のようになります。

```py
import pulp as pl

model = pl.LpProblem("Example", pl.LpMaximize)
solver = pl.PULP_CBC_CMD(msg=False)
x = pl.LpVariable('x')
y = pl.LpVariable('y')
model += x + y  # 目的関数
model += x + 2*y <= 4  # 制約条件
model += 4*x + y <= 8  # 制約条件は複数追加できる
result = model.solve(solver)
print(f"{x.name} = {x.value()}")  # x = 1.7142857
print(f"{y.name} = {y.value()}")  # y = 1.1428571
print(f"objective value = {model.objective.value()}")  # objective value = 2.8571428
```

このようなシンプルな線形計画問題では、手計算で各制約線の交点を求めることができます。最適解は次のように得られます；

$$
x =\dfrac{12}{7},\quad y=\dfrac{8}{7},\quad x+y = \dfrac{20}{7}
$$

上記のサンプルコードでも、同じ最適解が得られている事がわかります。


## ソルバの追加

以下のように、 `pulp` から呼び出すことができるソルバは複数あります。

```py
import pulp as pl
solver_list = pl.listSolvers()
print(solver_list)
# ['GLPK_CMD', 'PYGLPK', 'CPLEX_CMD', 'CPLEX_PY', 'GUROBI', 'GUROBI_CMD', 'MOSEK', 'XPRESS', 'XPRESS', 'XPRESS_PY', 'PULP_CBC_CMD', 'COIN_CMD', 'COINMP_DLL', 'CHOCO_CMD', 'MIPCL_CMD', 'SCIP_CMD', 'FSCIP_CMD', 'SCIP_PY', 'HiGHS', 'HiGHS_CMD', 'COPT', 'COPT_DLL', 'COPT_CMD']
```

`PULP_CBC_CMD` 以外はマシンにインストールすることで使用可能にする必要がありますが、これらのうち、MIT License でもある `HiGHS` は次のコマンドにより容易に用意することができます

```sh
uv add highspy
```

ソルバを変更するには、 `solver=pl.PULP_CBC_CMD()` の代わりに `solver=pl.HiGHS()` を指定することで計算に使用されます

```py
import pulp as pl

model = pl.LpProblem("Example", pl.LpMaximize)
solver = pl.HiGHS(msg=False)
x = pl.LpVariable('x')
y = pl.LpVariable('y')
model += x + y  # 目的関数
model += x + 2*y <= 4  # 制約条件
model += 4*x + y <= 8  # 制約条件は複数追加できる
result = model.solve(solver)
print(f"{x.name} = {x.value()}")  # x = 1.7142857142857144
print(f"{y.name} = {y.value()}")  # y = 1.1428571428571428
print(f"objective value = {model.objective.value()}")  # objective value = 2.857142857142857
```

pulp から呼び出せるソルバは他にもあり、例えば `SCIP_CMD` は Apache License 2.0 でもあり無償利用することができますが、ソースコードビルドの手順が必要な模様です。

## 参考文献

https://docs.astral.sh/uv/getting-started/installation/
https://coin-or.github.io/pulp/guides/how_to_configure_solvers.html
https://ergo-code.github.io/HiGHS/dev/interfaces/python/
https://www.scipopt.org/doc/html/LICENSE.php
https://zenn.dev/ohtaman/articles/advent2022_use_scip