整数計画問題

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

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

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

整数計画問題の例[編集]