整数多面体

【せいすうためんたい (integral polyhedron)】

凸多面体 $P=\{{\boldsymbol {x}}\mid {\boldsymbol {A}}{\boldsymbol {x}}\leq b\}\,$ において, $P_{I}\,$ を, 凸多面体 $P\,$ に含まれる整数ベクトルの集合の凸包とする. このとき $P=P_{I}\,$ となる $P\,$ を整数多面体という. 任意のコストベクトル ${\boldsymbol {c}}\,$ に対する整数多面体 $P=P_{I}\,$ 上での整数計画問題は$P\,$ 上での線形計画問題として解くことができる.