この記事について

整数計画で困ることのひとつが「非線形なものを扱いたい」という場面です。区分関数（$\max, \min$）、非凸な非線形関数、2次の積項…。これらを線形のMIPで表現できれば、既存のソルバー（Gurobi、CPLEX、HiGHS等）の強力なエンジンに乗せられます。

この記事では、区分線形近似と2値変数の積の線形化という2つの代表的なテクニックを紹介します。

非凸な非線形関数の区分線形近似

非凸な非線形関数 $f(x)$ を最小化したい場合、そのままだと整数計画では扱えません。そこで 区分線形関数 $g(x)$ で近似します。

ブレークポイント $a_1, a_2, \ldots, a_m$ を選び、その点での値 $f(a_i)$ を結んだ折れ線で近似します。ブレークポイントが多いほど近似精度は上がりますが、変数も増えるので計算が重くなります。

線分上の点の表現

区分線形関数の任意の点は「いずれかの線分上にある」ので、その線分の2端点の重み付き平均で書けます。

(x, g(x)) = t_i (a_i, f(a_i)) + t_{i+1} (a_{i+1}, f(a_{i+1}))

t_i + t_{i+1} = 1, \quad t_i, t_{i+1} \geq 0

これを全体に拡張すると、ブレークポイント $a_1, \ldots, a_m$ の重みベクトル $(t_1, \ldots, t_m)$ で：

(x, g(x)) = \sum_{i=1}^{m} t_i (a_i, f(a_i)), \quad \sum_{i=1}^{m} t_i = 1, \quad t_i \geq 0

$t_i$ のうち高々2つの隣り合うものだけが正でなければなりません。これがないと、隣同士でない2点の重み付き平均になってしまい、関数 $f$ と値がずれます。

「隣り合う2つだけが正」を整数計画で表現

各線分 $i$ に対応する2値変数 $z_i \in {0, 1}$ を導入し、「点が $i$ 番目の線分上にある」ことを表します。

\begin{aligned}
t_1 &\leq z_1 \\
t_i &\leq z_{i-1} + z_i, \quad i = 2, \ldots, m-1 \\
t_m &\leq z_{m-1} \\
\sum_{i=1}^{m-1} z_i &= 1 \\
z_i &\in \{0, 1\}
\end{aligned}

$z_i = 1$ なら点は $i$ 番目の線分上にある（$t_i$ と $t_{i+1}$ のみが正になり得る）
$\sum z_i = 1$ により、ちょうど1つの線分が選ばれる

これは SOS2（Special Ordered Set type 2） という制約タイプとして Gurobi・CPLEX に標準搭載されています。直接 SOS2 制約として渡せば、より効率的に処理してくれます。

Pythonで区分線形近似を実装

import numpy as np
import pulp

# 近似したい非線形関数（例：sin に少し小細工を加えた非凸関数）
def f(x):
    return np.sin(x) + 0.1 * x

# ブレークポイント
xs = np.linspace(0, 10, 11)   # 11点
fs = [f(x) for x in xs]
m = len(xs)

prob = pulp.LpProblem("piecewise", pulp.LpMinimize)

# 区分線形近似に使う変数
t = [pulp.LpVariable(f"t{i}", lowBound=0, upBound=1) for i in range(m)]
z = [pulp.LpVariable(f"z{i}", cat='Binary') for i in range(m-1)]

# x と g(x) を t で表現
x_var = pulp.lpSum(xs[i] * t[i] for i in range(m))
g_x   = pulp.lpSum(fs[i] * t[i] for i in range(m))

# 目的関数：g(x) を最小化
prob += g_x

# SOS2 制約（隣り合う2つの t のみが正）
prob += t[0] <= z[0]
for i in range(1, m-1):
    prob += t[i] <= z[i-1] + z[i]
prob += t[m-1] <= z[m-2]

prob += pulp.lpSum(t) == 1
prob += pulp.lpSum(z) == 1

prob.solve(pulp.PULP_CBC_CMD(msg=0))

x_opt = pulp.value(x_var)
g_opt = pulp.value(g_x)
print(f"近似解 x = {x_opt:.4f}")
print(f"近似 g(x) = {g_opt:.4f}")
print(f"真の f(x) = {f(x_opt):.4f}")

実行結果例：

近似解 x = 5.0000
近似 g(x) = -0.4589
真の f(x) = -0.4589

これで非凸関数の大域最適解に近い点を見つけられます。

2値変数の積を線形化する

2次計画問題（QP）や QUBO（Quadratic Unconstrained Binary Optimization）を MIP に変換するときに重要な技法です。

問題

\text{minimize} \quad \sum_{i=1}^{n} \sum_{j=1}^{n} q_{ij} x_i x_j

\text{subject to} \quad x_i \in \{0, 1\}

$x_i x_j$ の積項が非線形です。これを線形化したいです。

古典的な線形化

新しい2値変数 $y_{ij} \in {0, 1}$ を導入して $y_{ij} = x_i x_j$ を表します。$x_i, x_j \in {0,1}$ の組み合わせは4通り：

$x_i$	$x_j$	$x_i x_j$
0	0	0
1	0	0
0	1	0
1	1	1

これを満たすには3本の線形制約で十分です。

\begin{aligned}
y_{ij} &\leq x_i \\
y_{ij} &\leq x_j \\
y_{ij} &\geq x_i + x_j - 1 \\
y_{ij} &\in \{0, 1\}
\end{aligned}

確認

$x_i$	$x_j$	上限 $\min(x_i, x_j)$	下限 $x_i + x_j - 1$	$y_{ij}$
0	0	0	-1	0
1	0	0	0	0
0	1	0	0	0
1	1	1	1	1

線形化後の MIP

\begin{aligned}
\text{minimize} \quad & \sum_{i=1}^{n} \sum_{j=1}^{n} q_{ij} y_{ij} \\
\text{subject to} \quad & y_{ij} \leq x_i \\
& y_{ij} \leq x_j \\
& y_{ij} \geq x_i + x_j - 1 \\
& x_i \in \{0, 1\} \\
& y_{ij} \in \{0, 1\}
\end{aligned}

これで標準的なMIPソルバーで解けます。

Pythonでの実装：QUBO → MIP変換

import numpy as np
import pulp

# QUBO 行列の例（対称・非対角に交互作用あり）
np.random.seed(42)
n = 5
Q = np.random.randint(-5, 5, (n, n))
Q = (Q + Q.T) / 2   # 対称化

prob = pulp.LpProblem("qubo_to_mip", pulp.LpMinimize)

x = [pulp.LpVariable(f"x{i}", cat='Binary') for i in range(n)]
y = {(i, j): pulp.LpVariable(f"y{i}_{j}", cat='Binary')
     for i in range(n) for j in range(n)}

# 線形化された目的関数
prob += pulp.lpSum(Q[i][j] * y[(i, j)] for i in range(n) for j in range(n))

# 線形化制約
for i in range(n):
    for j in range(n):
        prob += y[(i, j)] <= x[i]
        prob += y[(i, j)] <= x[j]
        prob += y[(i, j)] >= x[i] + x[j] - 1

prob.solve(pulp.PULP_CBC_CMD(msg=0))

x_opt = [int(pulp.value(xi)) for xi in x]
print(f"x* = {x_opt}")
print(f"目的関数値 = {pulp.value(prob.objective):.2f}")

# 検証：直接 xQx を計算
x_np = np.array(x_opt)
direct = x_np @ Q @ x_np
print(f"直接計算 xQx = {direct:.2f}")

実行結果例：

x* = [0, 1, 0, 1, 1]
目的関数値 = -12.00
直接計算 xQx = -12.00

線形化した目的関数値と直接計算した $\mathbf{x}^\top Q \mathbf{x}$ が一致しています。これで非線形の2次問題を線形のMIPで解けました。

まとめ

区分線形近似：非凸な非線形関数 $f(x)$ をブレークポイントで折れ線近似
「隣り合う2つの重みのみが正」を SOS2 制約 で表現
2値変数の積の線形化：$y_{ij} = x_i x_j$ を3本の線形制約で表現
これによりQUBO（2次の0-1最適化）が MIP として解ける