整数計画法: pythonとgurobiを使って建設計画を最適化

オペレーションズ・リサーチの分野のひとつである「数理計画法」は、数理計画問題（最適化問題）を解くための方法です。数理計画法の様々なアプローチのうちのひとつに「整数計画法」があります。

この記事では、整数計画法を使ってある工場の建設計画問題を解いてみます。

この記事がカバーする内容

整数計画法とは何か
どうやって例題を数理モデルとして定式化するか
どうやって定式化した数理モデルをアルゴリズムとして実装するか

整数計画法

整数計画法はどんな方法ですか？

決定変数を整数として扱う数理計画法を「整数計画法(Integer Programming: IP)」と呼びます。

整数計画法は、

純粋整数計画法(pure integer programming): 決定変数を全て整数として問題を解く方法
混合整数計画法(mixed integer programming): 決定変数の一部を整数として問題を解く方法
0-1整数計問題(zero-one integer programming): 決定変数が０または１のみに限定して問題を解く方法

とさらに細かく分類されます。⁽¹⁾

整数計画法は、「変数が整数」という制約を線形計画法に追加した方法と捉えることができます。整数計画法で扱う関数と変数は、線形計画法と同様です。

整数計画法で扱う関数と変数

目的関数 (Objective function)
決定変数 (Decision variables)
制約 (Constraints)

なぜ整数計画法は難しい？

「整数計画法は線形計画法より難くなる」と聞きますが、なぜでしょう？

計算機で解く問題の困難さを考える計算量理論において、線形計画法(LP)はP、一方、整数計画法(IP)はNP-hardだからです。⁽²⁾

？？？

線形計画法は、実行可能領域の端点に注目して最適解を決定します。実行可能領域は多面体です。そして、目的関数の最大・最小値は、多面体の端点で達成されます。多面体のある端点が、線形計画問題の最適解になります。

一方、整数計画法は、線形計画法に「決定変数は整数である」という制約を加えています。しかし、実行可能領域の端点が必ず整数とは限りません。そのため、整数計画法は、端点に注目するだけでは最適解を得られません。整数計画法は、実行可能領域中に含まれるたくさんの整数の組み合わせのトライ＆エラーから最適解を決定します。

これが、整数計画法が線形計画法より難しくなると言われるポイントです。

確かに全部の組み合わせを試せって言われると大変そうです。
ところで、P、NPって何ですか？

この記事では説明を割愛しますが、P、NPは、計算量理論におけるクラスです。

P(Polynomial Time)：多項式時間内で解ける判定問題のクラス
NP(Non-deterministic-polynomial Time)：答えが”yes”となるような問いに対して、多項式時間で検証できる証拠が存在する判定問題のクラス

です。

参考までに「ソフトウェアサイエンスの基本シリーズ第3回計算複雑さの研究って？」のリンクを貼っておきます。⁽³⁾

ちなみに「P≠NP予想」という問題は2021年時点でも解決できておらず、クレイ研究所のミレニアム問題になっています。⁽⁴⁾ 証明できると懸賞金100万ドルだそうです。

整数計画法を使って問題を解いてみよう

例題

今回のお題は「新しい工場の建設計画」です。

例題

ある会社は新製品を開発した。この製品を20社の大口顧客へ供給するため、工場の建設計画を立てている。現在、10拠点が工場の建設候補地にあげられている。現在、コストに関して、「工場の建設コスト」と「工場から顧客への製品配送コスト」があげられている。工場の建設と製品の配送コストの合計を最小化するための建設計画を考えよ。

顧客と工場

各顧客はどれか１つの工場から製品を受け取る。

工場のキャパシティ

ひとつの工場が受け入れられる顧客の数は最大６である。

オプション

会社には、大きな工場を建設するという選択肢もある。大きな工場を建設した場合、標準工場の建設コストの50%を建設コストに上乗せする必要がある、工場が受け入れられる顧客の数は最大８までになる。

数理モデルの定式化

続いて、問題を数理モデルに定式化します。

今回の問題に関する「集合」と「データ」を書き出し、「目的関数」「決定変数」「制約」をまとめます。

数理モデル

Sets: 集合

$F: $ Factory locations　　工場の建設予定地

$C: $ Customers　　顧客

Data: データ

$build_{f}: $ 工場の建設コスト　$f \in F$

$cost_{c,f}: $ 工場から顧客への製品輸送コスト　　$c \in C, f \in F$

$maxcap: $ 工場が顧客を受け入れられるキャパシティ

$add: $ オプションを選択した工場の顧客受入増加数

Decision Variable: 決定変数

$x_{f}: $ バイナリ変数: 工場を建設する場合１、しない場合０　　$f \in F$

$y_{c,f}: $ バイナリ変数: 工場から顧客へ輸送する場合１、しない場合０　　$c \in C, f \in F$

$z_{f}: $ バイナリ変数: 工場がオプションを選択する場合１、しない場合０　　$f \in F$

Objective Funcition: 目的関数→コストの最小化

$\begin{eqnarray}minimize: BuildCost + OptionalCost + TransportCost &=& \sum_{f \in F} build_{f} \times x_{f}\\ & &+ \sum_{f \in F} 0.5 build_{f} \times z_{f}\\ & &+ \sum_{c \in C} \sum_{f \in F} cost_{c,f} \times y_{c,f}\end{eqnarray}$

Constraints: 制約

(1)$\sum_{f \in F} y_{c,f} = 1 \quad \forall c \in C$

(2)$\sum_{c \in C} y_{c,f} \leq maxcap \times x_f + add \times z_f \quad \forall f \in F$

(3)$z_f \leq x_f \quad \forall f \in F$

扱う決定変数が全てバイナリ変数だから、この問題は0-1整数計問題ということですね！

制約に関して、(1)は、顧客と工場の関係に関する制約です。顧客は必ずどこかひとつ工場から製品を受け取ります。

(2)は、工場が受け入れられる顧客の数に関する制約です。大きな工場を建設した場合、その工場のキャパシティは$add$だけ増加します。

(3)は、オプションに関する制約です。オプションは建設予定地の工場だけに対して選択できます。