全双対整数性

出典: ORWiki

【ぜんそうついせいすうせい (totally dual integrality (TDI))】

線形不等式システム $\boldsymbol{A} \boldsymbol{x} \leq \boldsymbol{b} \,$ が線形計画問題 $\max \{\boldsymbol{c} \boldsymbol{x} \mid \boldsymbol{A} \boldsymbol{x} \leq \boldsymbol{b} \} \,$ が有界であるような任意の整数ベクトル $\boldsymbol{c} \,$ に対して, その双対問題 $\min\{ \boldsymbol{b} \boldsymbol{y} \mid \boldsymbol{y} \boldsymbol{A} = \boldsymbol{c}, \boldsymbol{y} \geq \boldsymbol{0} \} \,$ が, 整数の最適解 $\boldsymbol{y}^* \,$ をもつならば, 全双対整数的 (totally dual integral, TDI) であるという.