整数計画問題

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

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

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

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

\begin{matrix} \underset{𝐱 \in ℤ^{n}}{maximize} & 𝐜^{T} 𝐱 \\ subject to & A 𝐱 \leq 𝐛, \\ 𝐱 \geq 𝟎 \end{matrix}

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

\begin{matrix} \underset{𝐱 \in ℤ^{n}}{maximize} & 𝐜^{T} 𝐱 \\ subject to & A 𝐱 + 𝐬 = 𝐛, \\ 𝐬 \geq 𝟎, \\ 𝐱 \geq 𝟎, \end{matrix}

ここで $A \in ℝ^{m \times n}$ は行列、 $𝐛 \in ℝ^{m}, 𝐜 \in ℝ^{n}$ は列ベクトルである。線形計画問題と同様に、不等式の制約式に対して非負の制約をもつテンプレート:仮リンク $𝐬 \geq 𝟎$ を不等式制約式の小さな項に対して導入することで等式の制約式に書き換えられ、 $𝐱 \geq 𝟎$ という非負の条件を持たない自由変数に対しては、非負の変数 $𝐱^{+} \geq 𝟎$ , $𝐱^{-} \geq 𝟎$ を用いて、 $𝐱 = 𝐱^{+} - 𝐱^{-}$ と書き直すことで、整数計画問題を標準形に表すことができる。

例

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

\begin{matrix} \underset{x, y \in ℤ}{maximize} & y \\ subject to & - x + y \leq 1 \\ 3 x + 2 y \leq 12 \\ 2 x + 3 y \leq 12 \\ x, y \geq 0 \end{matrix}

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

類似の問題

テンプレート:Visible anchor（Mixed-integer linear programming: MILP) とは、変数の一部分に対して整数条件が課された問題である。

テンプレート:Visible anchor（Zero–one linear programming、binary integer programming）とは、変数の取り得る値が 0 または 1 に限定された問題である。整数変数が有界の場合はテンプレート:仮リンクを用いて表現することができる^[2]^[3]。具体例として、整数変数が $0 \leq x \leq U$ の範囲であるとき、変数は $⌊ \log_{2} U ⌋ + 1$ 個のバイナリ変数を用いて:

x = x_{1} + 2 x_{2} + 4 x_{3} + \dots + 2^{⌊ \log_{2} U ⌋} x_{⌊ \log_{2} U ⌋ + 1} .

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

\begin{matrix} x = x_{1} + 2 x_{2} + 3 x_{3} + \dots + U x_{U}, \\ x_{1} + x_{2} + x_{3} + \dots + x_{U} \leq 1 . \end{matrix}

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

\begin{matrix} x = x_{1} + x_{2} + x_{3} + \dots + x_{U} . \\ (x_{1} \geq x_{2} \geq x_{3} \geq \dots \geq x_{U}) . \end{matrix}

と書き換えられる。