整数計画問題

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

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

整数計画問題の例

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