全双対整数性

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

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