全双対整数性

【ぜんそうついせいすうせい (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) であるという.