整数多面体

出典: ORWiki

【せいすうためんたい (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 \,$ 上での線形計画問題として解くことができる.