整数計画問題

整数計画問題（せいすうけいかくもんだい）は、線型計画問題において、解ベクトルxの各要素を整数に限定した問題をいう。これはNP困難な問題に該当する。線型計画問題には多項式時間アルゴリズムが存在するのに対し、整数計画問題ではまだ見つかっていない。

解ベクトルxの各要素を0または1のみに限定したものを、特に0-1整数計画問題という。

整数計画問題の基準形と標準形

整数計画問題では、定式化を標準形（standard form）および基準形（canonical form）に従った形式で表される。基準形の整数計画問題は次のように書き表される（このときベクトル $\mathbf {x}$ について求める問題である）:

${\begin{aligned}&{\underset {\mathbf {x} \in \mathbb {Z} ^{n}}{\text{maximize}}}&&\mathbf {c} ^{\mathrm {T} }\mathbf {x} \\&{\text{subject to}}&&A\mathbf {x} \leq \mathbf {b} ,\\&&&\mathbf {x} \geq \mathbf {0} \end{aligned}}$

また標準形の整数計画問題は次のように書き表される:

${\begin{aligned}&{\underset {\mathbf {x} \in \mathbb {Z} ^{n}}{\text{maximize}}}&&\mathbf {c} ^{\mathrm {T} }\mathbf {x} \\&{\text{subject to}}&&A\mathbf {x} +\mathbf {s} =\mathbf {b} ,\\&&&\mathbf {s} \geq \mathbf {0} ,\\&&&\mathbf {x} \geq \mathbf {0} ,\end{aligned}}$

ここで $A\in \mathbb {R} ^{m\times n}$ は行列、$\mathbf {b} \in \mathbb {R} ^{m},\mathbf {c} \in \mathbb {R} ^{n}$ は列ベクトルである。線形計画問題と同様に、不等式の制約式に対して非負の制約をもつスラック変数$\mathbf {s} \geq \mathbf {0}$を不等式制約式の小さな項に対して導入することで等式の制約式に書き換えられ、$\mathbf {x} \geq \mathbf {0}$ という非負の条件を持たない自由変数に対しては、非負の変数 $\mathbf {x^{+}} \geq \mathbf {0}$, $\mathbf {x^{-}} \geq \mathbf {0}$ を用いて、$\mathbf {x} {=}\mathbf {x^{+}} -\mathbf {x^{-}}$ と書き直すことで、整数計画問題を標準形に表すことができる。

例

IPとLP緩和後の多面体

右の図に対する整数計画問題は以下の通りである:

${\begin{aligned}{\underset {x,y\in \mathbb {Z} }{\text{maximize}}}\quad &y\\{\text{subject to}}\quad &-x+y\leq 1\\&3x+2y\leq 12\\&2x+3y\leq 12\\&x,y\geq 0\end{aligned}}$

ここで赤点は実行可能な整数点を表しており、赤の破線は実行可能な点をすべて含む最小の多面体（凸包）を表している。青い線と座標軸によって定義されるのが、制約条件から整数制約を除いた線形計画（LP）緩和の多面体を表している。最適化の目標としては、黒の破線が多面体に接した状態を維持したまま可能な限り上方に移動させることである。整数問題の最適解は $(1,2)$, $(2,2)$ で、目的関数値が $2$ である。一方、変数の整数条件を取り除いた線形計画緩和の最適解は $(1.8,2.8)$ で、目的関数値は $2.8$ である。この線形計画緩和の最適解に対して小数部分を最も近い整数に丸めると、$(2,3)$ となり、整数計画問題の実行可能解ではない。

変種問題

混合整数線形計画問題（Mixed-integer linear programming: MILP) とは、変数の一部分に対して整数条件が課された問題である。

0-1整数計画問題（Zero–one linear programming、binary integer programming）とは、変数の取り得る値が 0 または 1 に限定された問題である。整数変数が有界の場合はバイナリ変数を用いて表現することができる。具体例として、整数変数が $0\leq x\leq U$ の範囲であるとき、変数は $\lfloor \log _{2}U\rfloor +1$ 個のバイナリ変数を用いて:

$$x=x_{1}+2x_{2}+4x_{3}+\cdots +2^{\lfloor \log _{2}U\rfloor }x_{\lfloor \log _{2}U\rfloor +1}.$$

もしくは、$U$ 個のバイナリ変数を用いて:

$${\begin{aligned}x=x_{1}+2x_{2}+3x_{3}+\cdots +Ux_{U},\\x_{1}+x_{2}+x_{3}+\cdots +x_{U}\leq 1.\end{aligned}}$$

もしくは、$U$ 個のバイナリ変数を用いて:

$${\begin{aligned}x=x_{1}+x_{2}+x_{3}+\cdots +x_{U}.\\(x_{1}\geq x_{2}\geq x_{3}\geq \cdots \geq x_{U}).\end{aligned}}$$

と書き換えられる。

整数計画問題として解かれる問題の例

• 頂点被覆問題
• ナップサック問題
• ハミルトン閉路問題
• 巡回セールスマン問題
• 集合被覆問題
• 施設配置問題
• 最大独立集合問題
• 最小極大マッチング問題
• 最大クリーク問題
• 支配集合問題
• 辺支配集合問題
• ビンパッキング問題
• 一般化割当問題

参考図書

和書：

• 今野浩:「整数計画法」，産業図書，1981．
• 今野浩・鈴木久敏編：「整数計画と組合せ最適化」，日科技連，1982.
• 久保幹雄，田村明久，松井知己（編）：「応用数理計画ハンドブック」，朝倉書店，2002.

洋書：