整数計画問題

提供: miniwiki
2015/4/1/ (水) 01:51時点における2001:df0:2ed:4321:b02b:593c:3ffa:f485 (トーク)による版
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)
移動先:案内検索

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

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

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