離散最適化

離散最適化（discrete optimization）は、変数が整数や0-1といった離散値をとる最適化問題の総称。連続最適化と異なり、目的関数の微分が使えないため、独自の解法が必要になる。

問題の分類¶

連続変数$x \in \mathbb{R}^n$の問題をLP緩和（LP relaxation）と呼ぶ。LP緩和の最適値は元の整数計画の最適値の上界（最小化問題では下界）を与える。

代表的な問題¶

• ナップサック問題：重量制約のもとで価値最大化 → knapsack_problem

• 最短路問題：グラフ上の最短経路 → shortest_path_problem

• 巡回セールスマン問題（TSP）：すべての都市を一度ずつ訪問する最短ルート

• 施設配置問題（facility location）：コスト最小の施設配置と割り当て

• グラフ彩色問題：隣接する頂点が異なる色になるよう最少色数で彩色

解法¶

厳密解法¶

分岐限定法（branch and bound）が最も広く使われる。LP緩和で上界（下界）を計算しながら、変数を整数に固定して探索木を枝刈りしていく。

1. LP緩和を解いて最適値の限界（bound）を得る

2. 非整数の変数$x_j = \alpha$に対して$x_j \leq \lfloor \alpha \rfloor$と$x_j \geq \lceil \alpha \rceil$に分岐（branch）

3. 子ノードのLP緩和の最適値が現在の最良解より悪ければ枝刈り

4. すべての変数が整数になったら実行可能解として更新

カット平面法（cutting plane method）は、LP緩和の実行可能領域を切る不等式（カット）を追加して整数解に収束させる方法。分岐限定法と組み合わせた分岐カット法（branch and cut）が現代ソルバーの基本手法。

動的計画法は部分問題への再帰で解く。ナップサック問題は$O(nV)$で解ける（擬多項式時間）。

近似解法・ヒューリスティクス¶

厳密解が計算困難（NP困難）な場合に用いる。

ソルバー¶

整数計画問題は PuLP や OR-Tools などで定式化し、バックエンドのソルバーに渡す。

PuLPによる定式化例¶

import pulp

# 問題の定義（最大化）
prob = pulp.LpProblem("example", pulp.LpMaximize)

# 変数（0-1整数）
x = [pulp.LpVariable(f"x{i}", cat="Binary") for i in range(3)]

# 目的関数
prob += 5 * x[0] + 4 * x[1] + 3 * x[2]

# 制約
prob += 2 * x[0] + 3 * x[1] + x[2] <= 5

# 求解
prob.solve(pulp.PULP_CBC_CMD(msg=0))

for v in prob.variables():
    print(f"{v.name} = {v.varValue}")
# => x0=1, x1=1, x2=0  (value=9)

計算複雑性¶

多くの組合せ最適化問題はNP困難であり、一般に多項式時間の厳密解法は存在しないと考えられている。

参考文献¶

• 寒野善博（2019）『最適化手法入門』、講談社サイエンティフィック

• 茨木俊秀（2001）『組合せ最適化入門』、講談社

• 離散最適化とはどんな分野か - パンの木を植えて

• 数理最適化用語集 — MSI