整数計画法(Integer Programming, IP)は、決定変数が整数値を取る最適化問題を解くための手法です。ナップサック問題や巡回セールスマン問題、スケジューリング問題など、現実世界の多くの離散最適化問題を定式化して解くことができます。
連続最適化と異なり、離散最適化問題の多くはNP困難であり、問題サイズが大きくなると計算時間が指数的に増加します。しかし、分枝限定法などの手法とソルバーの発展により、実用的な規模の問題が解けるようになっています。
本記事の内容
- 整数計画問題の定式化
- 線形計画法との関係
- ナップサック問題の定式化と実装
- 巡回セールスマン問題の概要
整数計画問題の定式化
一般的な整数計画問題は以下のように定式化されます。
$$ \begin{align} \min_{\bm{x}} \quad & \bm{c}^T\bm{x} \\ \text{subject to} \quad & \bm{A}\bm{x} \leq \bm{b} \\ & \bm{x} \in \mathbb{Z}^n \end{align} $$
ここで $\bm{x} \in \mathbb{Z}^n$ は整数値の決定変数、$\bm{c}$ は目的関数の係数、$\bm{A}\bm{x} \leq \bm{b}$ は制約条件です。
特に決定変数が $\{0, 1\}$ のみを取る場合を 0-1整数計画問題（二値計画問題）と呼びます。
線形計画法との関係
整数制約を外して連続変数として解いたものを LP緩和(LP relaxation) と呼びます。
$$ \begin{align} \min_{\bm{x}} \quad & \bm{c}^T\bm{x} \\ \text{subject to} \quad & \bm{A}\bm{x} \leq \bm{b} \\ & \bm{x} \geq \bm{0} \end{align} $$
LP緩和の最適値は、元の整数計画問題の最適値の下界（最小化の場合）を与えます。この性質は分枝限定法で利用されます。
代表的な離散最適化問題
| 問題 | 計算量 |
|---|---|
| 最大マッチング問題 | 多項式時間 |
| 最大流問題 | 多項式時間 |
| 最小費用流問題 | 多項式時間 |
| 巡回セールスマン問題 | NP困難 |
| ナップサック問題 | NP困難 |
| ビンパッキング問題 | NP困難 |
| 最大独立集合問題 | NP困難 |
NP困難な問題であっても、整数計画ソルバー（Gurobi, CPLEX, CBC等）を利用することで、実用的なサイズの問題を解くことができます。
ナップサック問題
問題の定義
$n$ 個のアイテムがあり、アイテム $i$ の重さが $w_i$、価値が $v_i$ です。容量 $W$ のナップサックに入れるアイテムの組み合わせを選び、価値の合計を最大化します。
$$ \begin{align} \max_{\bm{x}} \quad & \sum_{i=1}^{n} v_i x_i \\ \text{subject to} \quad & \sum_{i=1}^{n} w_i x_i \leq W \\ & x_i \in \{0, 1\}, \quad i = 1, \dots, n \end{align} $$
$x_i = 1$ はアイテム $i$ を選択することを意味します。
PuLPによる実装
import numpy as np
import matplotlib.pyplot as plt
from pulp import LpMaximize, LpProblem, LpVariable, lpSum, value
np.random.seed(42)
# --- ナップサック問題のデータ ---
n_items = 15
weights = np.random.randint(1, 20, n_items)
values = np.random.randint(5, 50, n_items)
capacity = int(np.sum(weights) * 0.4)
print(f"アイテム数: {n_items}")
print(f"ナップサック容量: {capacity}")
print(f"アイテムの重さ: {weights}")
print(f"アイテムの価値: {values}")
# --- PuLPで定式化 ---
prob = LpProblem("Knapsack", LpMaximize)
# 決定変数（0-1変数）
x = [LpVariable(f"x_{i}", cat="Binary") for i in range(n_items)]
# 目的関数: 価値の最大化
prob += lpSum(values[i] * x[i] for i in range(n_items))
# 制約条件: 重さの合計 <= 容量
prob += lpSum(weights[i] * x[i] for i in range(n_items)) <= capacity
# 求解
prob.solve()
# --- 結果の表示 ---
selected = [i for i in range(n_items) if value(x[i]) == 1]
total_value = sum(values[i] for i in selected)
total_weight = sum(weights[i] for i in selected)
print(f"\n=== 最適解 ===")
print(f"選択されたアイテム: {selected}")
print(f"合計価値: {total_value}")
print(f"合計重さ: {total_weight} / {capacity}")
# --- 可視化 ---
fig, ax = plt.subplots(figsize=(12, 5))
colors = ['green' if i in selected else 'gray' for i in range(n_items)]
x_pos = np.arange(n_items)
bars = ax.bar(x_pos, values, color=colors, alpha=0.7, edgecolor='black')
ax.set_xlabel('Item Index')
ax.set_ylabel('Value')
ax.set_title(f'Knapsack Problem (Capacity={capacity}, Total Value={total_value})')
# 重さを表示
for i, (bar, w) in enumerate(zip(bars, weights)):
ax.text(bar.get_x() + bar.get_width()/2., bar.get_height() + 0.5,
f'w={w}', ha='center', va='bottom', fontsize=8)
ax.legend(['Selected', 'Not Selected'], loc='upper right')
ax.grid(True, alpha=0.3)
plt.tight_layout()
plt.show()
巡回セールスマン問題の概要
巡回セールスマン問題(Traveling Salesman Problem, TSP)は、$n$ 個の都市を全て1回ずつ訪問して出発点に戻る最短経路を求める問題です。
$$ \begin{align} \min \quad & \sum_{i=1}^{n}\sum_{j=1}^{n} d_{ij} x_{ij} \\ \text{subject to} \quad & \sum_{j=1}^{n} x_{ij} = 1, \quad \forall i \\ & \sum_{i=1}^{n} x_{ij} = 1, \quad \forall j \\ & x_{ij} \in \{0, 1\} \end{align} $$
ここで $d_{ij}$ は都市 $i$ から $j$ への距離、$x_{ij} = 1$ は都市 $i$ から $j$ へ移動することを意味します。ただし、部分巡回を防ぐための追加制約（MTZ制約など）も必要です。
import numpy as np
import matplotlib.pyplot as plt
np.random.seed(42)
# TSPの例（貪欲法による近似解）
n_cities = 20
cities = np.random.rand(n_cities, 2) * 100
# 距離行列
dist_matrix = np.sqrt(((cities[:, None] - cities[None, :]) ** 2).sum(axis=2))
# 最近傍法（貪欲法）
def nearest_neighbor_tsp(dist_matrix, start=0):
n = len(dist_matrix)
visited = [start]
current = start
for _ in range(n - 1):
dists = dist_matrix[current].copy()
dists[visited] = np.inf
next_city = np.argmin(dists)
visited.append(next_city)
current = next_city
return visited
route = nearest_neighbor_tsp(dist_matrix)
total_dist = sum(dist_matrix[route[i], route[(i+1) % n_cities]] for i in range(n_cities))
# 可視化
fig, ax = plt.subplots(figsize=(8, 8))
for i in range(n_cities):
j = (i + 1) % n_cities
ax.plot([cities[route[i], 0], cities[route[j], 0]],
[cities[route[i], 1], cities[route[j], 1]], 'b-', alpha=0.5)
ax.scatter(cities[:, 0], cities[:, 1], c='red', s=100, zorder=5)
for i, (x, y) in enumerate(cities):
ax.annotate(str(i), (x, y), textcoords="offset points",
xytext=(5, 5), fontsize=8)
ax.set_title(f'TSP Nearest Neighbor (Distance={total_dist:.2f})')
ax.set_xlabel('x')
ax.set_ylabel('y')
ax.grid(True, alpha=0.3)
plt.tight_layout()
plt.show()
まとめ
本記事では、整数計画法の基礎について解説しました。
- 整数計画法は決定変数が整数値を取る最適化問題を解く手法
- LP緩和は整数制約を外した緩和問題で、最適値の下界を与える
- ナップサック問題はPuLPなどのソルバーで効率的に解くことができる
- 巡回セールスマン問題はNP困難だが、近似解法やソルバーにより実用的なサイズの問題を解ける
次のステップとして、以下の記事も参考にしてください。