整数計画問題#

読み: せいすうけいかくもんだい
英名: Integer Programming Problem
別名: IP

整数変数を含む最適化問題のことを整数計画問題と呼ぶ．なお，特に全ての変数についてとりうる値を 0 または 1 に限定した場合については 0-1 整数計画問題と呼んでいる．また，整数値を取る変数と実数値を取る変数が混在している場合は混合整数計画問題と呼ぶ．二次計画問題となる混合整数計画問題は，混合整数二次計画問題と呼ぶ．

ナップサック問題や巡回セールスマン問題などが整数計画問題の代表例として挙げられる．また，割当問題やシフトスケジューリングを整数計画問題として定式化し，解くことも行なわれている．なお，整数計画問題の代表的な解法として分枝限定法がある．