この記事はノバセル Advent Calendar 23日目です。

こんにちは。ノバセルにてデータサイエンティストをしています、石川ナディーム(@nadeemishikawa)です。数理最適化とは、制約条件のもとで目的関数を最大化または最小化する手法です。ビジネス上のさまざまな課題（生産計画、輸送計画、プライシングなど）や、機械学習モデルのハイパーパラメータ調整など、幅広い分野で用いられています。 Pythonで、数理最適化を扱うためのライブラリとしてオープンソースのPuLPがあります。本記事では、PuLPのインストール方法から、簡単な例としてナップサック問題を解く一連の流れをサクッと解説します。

PuLPとは

PuLPは、Pythonで簡単に使える数理最適化問題を解くPythonライブラリです。 Pythonコード内で問題の変数や制約、目的関数をシンプルに定義でき、最適化問題を解くことができます。PuLPの登場により、数理最適化を手軽に試せるようになり、さまざまな分野で利用されています。

PuLPのインストール

PuLPはpip installで簡単にインストールできます。

pip install pulp

インストール後、Python環境で以下を実行して問題なくimportできれば準備完了です。

import pulp
print(pulp.__version__)

ナップサック問題を用いた基本的な使い方の説明

ここからは、PuLPを使った問題定式化から数理最適化までの流れを「ナップサック問題」を例にサクッと紹介します。ナップサック問題とは、与えられたアイテム（各アイテムには価値と重量がある）から、ナップサックの容量上限を超えないようにアイテムを選択し、その総価値を最大化する問題です。

問題設定概要

ナップサック容量：W = 20
アイテム：以下の4品
- アイテムA：価値15、重量5『最大1つまで』
- アイテムB：価値7、重量4
- アイテムC：価値12、重量6
- アイテムD：価値1、重量1

モデル作成

変数の定義

アイテムごとに選択する個数を表す変数を定義します。以降の項目の変数はそれぞれのアイテムの個数を表します。

目的関数の定義

全ての選んだアイテムの総価値を最大化します。

制約条件の定義

ナップサックの容量が20を超えることはできません。
アイテムAは最大1つまでしか選べません。

変数領域の定義

全ての変数は非負整数です。

サンプルコード解説

Step 1: 数理最適化モデルの定義

ここでは、PuLPを用いて数理モデルを定義します。

第一引数には任意の名前を文字列で渡します。ここではKnapsackProblemという名前を付けています。第二引数では、pulp.LpMaximizeまたはpulp.LpMinimizeを指定して、問題が最大化問題か最小化問題か指定します。ここでは、ナップサックの総価値をできるだけ「大きく」したいのでpulp.LpMaximizeを選びます。

import pulp

# 問題の種類を最大化問題として定義
problem = pulp.LpProblem("KnapsackProblem", pulp.LpMaximize)

Step 2 : 変数の定義

ここでは、「アイテムAを何個」「アイテムBを何個」... のような変数を定義します。各変数は非負整数で、アイテムの個数を表します。 pulp.LpVariable()は、最適化問題で用いる変数を生成します。

第一引数は変数名（文字列）。 lowBoundは変数の下限値を指定。 upBoundは変数の上限値を指定。 catは変数の型を指定できます。pulp.LpIntegerは整数型、pulp.LpContinuousは連続値、pulp.LpBinaryは2値変数など。

アイテムAに関しては、最大1つまでという制約があるので upBound=1としています。一方、他のアイテムB, C, Dは上限を設けず、必要なら何個でも選べるようにしています。

# 各アイテムの変数を作成
x_A = pulp.LpVariable("A", lowBound=0, upBound=1, cat=pulp.LpInteger)  # 最大1つまで
x_B = pulp.LpVariable("B", lowBound=0, cat=pulp.LpInteger)
x_C = pulp.LpVariable("C", lowBound=0, cat=pulp.LpInteger)
x_D = pulp.LpVariable("D", lowBound=0, cat=pulp.LpInteger)

Step 3: 目的関数の定義

problem += ... は、ここで定義する目的関数や制約を問題インスタンスに追加することを意味します。ここでは、ナップサックに入れるアイテムによる「価値」の合計を最大化したいので、目的関数は「(アイテムAの選択数×Aの価値) + (アイテムBの選択数×Bの価値) + ...」となります。

目的関数はpulp.LpProblemインスタンス（ここではproblem）に対して1回だけ指定します。

# 選択されたアイテムの総価値を最大化する
problem += 15 * x_A + 7 * x_B + 12 * x_C + 1 * x_D

Step 4: 制約条件の定義

最大価値を得たいといっても、以下の制約を考慮しなければいけません、

「選んだアイテムの重量の合計が20を超えない」という容量制約
「アイテムAは最大1つまで」という制約

problem += **制約式** の形で制約を追加します。制約式は不等式または等式（<=, >=, ==）で表します。

Step2で既にx_AのupBound=1で「Aは最大1個」とはしていますが、以下のように記述することもできます。(ここではupBoundで指定したので厳密には不要ですが、例として記載。)

# 総重量がナップサックの容量を超えないように制約を追加
problem += 5 * x_A + 4 * x_B + 6 * x_C + 1 * x_D <= 20

# アイテムAは最大1つまで（今回はStep2で制約を追加済なため不要）
problem += x_A <= 1

Step 5: 最適化実行

problem.solve()で、定義した数理モデルを解きます。

# 最適化の実行
problem.solve()

Step 6: 解の表示

pulp.LpStatus[problem.status]で、最適化結果のステータス（Optimal, Infeasible, Unboundedなど）を表示できます。 pulp.value(x_A)のようにpulp.value()を使うことで、解（変数の値）を取得できます。 pulp.value(problem.objective)で最終的な目的関数の値（ここでは価値の合計）を取得できます。

# 最適化の結果を表示
print("Status:", pulp.LpStatus[problem.status])
print("Selected items:")
print(f"  A: {pulp.value(x_A)} 個")
print(f"  B: {pulp.value(x_B)} 個")
print(f"  C: {pulp.value(x_C)} 個")
print(f"  D: {pulp.value(x_D)} 個")
print("Total Value:", pulp.value(problem.objective))

出力結果：

Status: Optimal
Selected items:
  A: 1.0 個
  B: 0.0 個
  C: 2.0 個
  D: 3.0 個
Total Value: 42.0

ここから、「アイテムAを1個、アイテムCを2個、アイテムDを3個選ぶと、総価値は42で最大となる」ということが分かります。

コード全体

以下に全コードを掲載します。

import pulp

# Step 1: 数理モデルの定義
problem = pulp.LpProblem("KnapsackProblem", pulp.LpMaximize)

# Step 2 : 変数の定義
x_A = pulp.LpVariable("A", lowBound=0, upBound=1, cat=pulp.LpInteger)
x_B = pulp.LpVariable("B", lowBound=0, cat=pulp.LpInteger)
x_C = pulp.LpVariable("C", lowBound=0, cat=pulp.LpInteger)
x_D = pulp.LpVariable("D", lowBound=0, cat=pulp.LpInteger)

# Step 3: 目的関数の定義
problem += 15 * x_A + 7 * x_B + 12 * x_C + 1 * x_D

# Step 4: 制約条件の定義
problem += 5 * x_A + 4 * x_B + 6 * x_C + 1 * x_D <= 20
problem += x_A <= 1

# Step 5: 最適化実行
problem.solve()

# Step 6: 解の表示
print("Status:", pulp.LpStatus[problem.status])
print("Selected items:")
print(f"  A: {pulp.value(x_A)} 個")
print(f"  B: {pulp.value(x_B)} 個")
print(f"  C: {pulp.value(x_C)} 個")
print(f"  D: {pulp.value(x_D)} 個")
print("Total Value:", pulp.value(problem.objective))

まとめ

本記事では、PuLPを用いたナップサック問題の解法についての入門的な内容を紹介しました。実際に実務で数理最適化を用いる際は、事業への圧倒的解像度、ステークホルダーとの会話や適切な問題設定が鍵となり、難易度は高いです。しかし、こうした数理最適化問題に取り組むことで得られる思考法は、数理最適化問題に限らず、日々の問題解決能力を高めるうえでも有益なものとなると感じています。 PuLPは、今回のような単純なナップサック問題に限らず、複数のマーケティング施策の予算最適化やクーポン配布による利益最大化等、さまざまな数理最適化問題に応用可能です。この記事を足掛かりに、最適化問題へのアプローチをぜひ深めてみてください。

RAKSUL TechBlog

RAKSULグループのエンジニアが技術トピックを発信するブログです

【Python】PuLPで始める数理最適化