全整数計画

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

最適化問題において, すべての変数が整数値をとるものを, 全整数計画問題と呼ぶ. 全整数計画問題は, 整数値を表すのに, 複数の 0-1変数を使う事によって, 0-1整数計画問題に変形することができるが, このような変形は一般に解法の効率を落とす事が多い. 全整数計画問題は, 整数値をとる変数を連続変数に緩和した線形緩和問題を手がかりにした分枝限定法を用いて解くことが多い.