整数計画

【せいすうけいかく (integer programming)】

最適化問題において, 変数が整数値を取るという制約がいくつかの変数に付いているとき, これを整数計画と呼ぶ. 整数値を取る変数は, 整数変数と呼ばれる. 整数計画問題は, NP困難と呼ばれる問題クラスに属しており, 厳密解をいつでも効率的に求める算法の存在は, 理論的に絶望視されている. しかしながら, 様々な技法の開発と計算機の高性能化に伴い, 実用的には十分短い計算時間で解ける問題のクラスとサイズは, いまも広がり続けている.