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