整数計画問題のソースを表示

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

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

== 整数計画問題の基準形と標準形 ==
整数計画問題では、定式化を標準形（standard form）および基準形（canonical form）に従った形式で表される。基準形の整数計画問題は次のように書き表される（このときベクトル <math>\mathbf{x}</math> について求める問題である）<ref name="optBook">{{cite book|last1=Papadimitriou|first1=C. H.|author1-link=クリストス・パパディミトリウ|last2=Steiglitz|first2= K.|author2-link=:en:Kenneth Steiglitz|title=Combinatorial optimization: algorithms and complexity|year=1998|publisher=Dover|location=Mineola, NY|isbn=0486402584}}</ref>: 

:<math> \begin{align}
& \underset{\mathbf{x} \in \mathbb{Z}^n}{\text{maximize}}   && \mathbf{c}^\mathrm{T} \mathbf{x}\\
& \text{subject to} && A \mathbf{x} \le \mathbf{b}, \\
&  && \mathbf{x} \ge \mathbf{0}
\end{align} </math>

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

:<math> \begin{align}
& \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} \ge \mathbf{0}, \\
&  && \mathbf{x} \ge \mathbf{0},
\end{align} </math>
ここで <math>A \in \mathbb{R}^{m \times n}</math> は行列、<math>\mathbf{b} \in \mathbb{R}^m, \mathbf{c}\in \mathbb{R}^n</math> は列ベクトルである。[[線形計画問題]]と同様に、不等式の制約式に対して非負の制約をもつ{{仮リンク|スラック変数|en|slack variable}}<math>\mathbf{s} \ge \mathbf{0}</math>を不等式制約式の小さな項に対して導入することで等式の制約式に書き換えられ、<math>\mathbf{x} \ge \mathbf{0}</math> という非負の条件を持たない自由変数に対しては、非負の変数 <math>\mathbf{x^+} \ge \mathbf{0}</math>, <math>\mathbf{x^-} \ge \mathbf{0}</math> を用いて、<math>\mathbf{x}{{=}}\mathbf{x^+}-\mathbf{x^-}</math> と書き直すことで、整数計画問題を[[標準形]]に表すことができる。

== 例 ==
[[File:IP polytope with LP relaxation.svg|350px|thumb|IPとLP緩和後の多面体]]
右の図に対する整数計画問題は以下の通りである: 

:<math> \begin{align}
\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 \ge 0
\end{align} </math>

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

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

'''{{visible anchor|0-1整数計画問題}}'''（Zero–one linear programming、binary integer programming）とは、変数の取り得る値が 0 または 1 に限定された問題である。整数変数が有界の場合は{{仮リンク|バイナリ変数|en|binary data}}を用いて表現することができる<ref>{{cite book|last=Williams|first=H.P.|title=Logic and integer programming|series=International Series in Operations Research & Management Science|year=2009|volume=130|isbn= 978-0-387-92280-5}}</ref><ref>{{Cite journal |和書 |author=藤江哲也 |year=2012 |title=整数計画法による定式化入門 |journal=オペレーションズ・リサーチ |publisher=日本オペレーションズ・リサーチ学会 |volume=57 |issue=4 |page=190-197 |issn=00303674 }}</ref>。具体例として、整数変数が <math>0\le x\le U</math> の範囲であるとき、変数は <math>\lfloor \log_2U\rfloor+1</math> 個のバイナリ変数を用いて: 
:<math display=block>
x = x_1+2x_2+4x_3+\cdots+2^{\lfloor \log_2U\rfloor}x_{\lfloor \log_2U\rfloor+1}.
</math>

もしくは、<math>U</math> 個のバイナリ変数を用いて: 
:<math display=block>\begin{align}
x = x_1+2x_2+3x_3+\cdots+Ux_U, \\
x_1+x_2+x_3+\cdots+x_U \le 1.
\end{align}</math>

もしくは、<math>U</math> 個のバイナリ変数を用いて: 
:<math display=block>\begin{align}
x = x_1+x_2+x_3+\cdots+x_U. \\
(x_1 \ge x_2 \ge x_3 \ge \cdots \ge x_U).
\end{align}</math>

と書き換えられる。

== 整数計画問題として解かれる問題の例 ==
*[[頂点被覆問題]]
*[[ナップサック問題]]
*[[ハミルトン閉路問題]]
*[[巡回セールスマン問題]]
*[[集合被覆問題]]
*[[施設配置問題]]
*[[最大独立集合問題]]
*[[最小極大マッチング問題]]
*[[最大クリーク問題]]
*[[支配集合問題]]
*[[辺支配集合問題]]
*[[ビンパッキング問題]]
*[[一般化割当問題]]

== 脚注 ==
{{脚注ヘルプ}}
{{Reflist}}

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

{{主要な最適化問題の分類}}
{{最適化アルゴリズム}}

{{DEFAULTSORT:せいすうけいかくもんたい}}
[[Category:最適化]]
[[Category:数学に関する記事]]