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

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

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

編集

参考になり得る図書

編集

和書:

  • 今野浩:「整数計画法」,産業図書,1981.
  • 今野浩・鈴木久敏編:「整数計画と組合せ最適化」,日科技連,1982.
  • 久保幹雄,田村明久,松井知己(編):「応用数理計画ハンドブック」,朝倉書店,2002.

洋書: