全双対整数性

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

線形不等式システム $\mathbf {A} \mathbf {x} \leq \mathbf {b} \,$ が線形計画問題 $\max\{\mathbf {c} \mathbf {x} \mid \mathbf {A} \mathbf {x} \leq \mathbf {b} \}\,$ が有界であるような任意の整数ベクトル 構文解析に失敗 (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \mathbf {c} \,} に対して, その双対問題 構文解析に失敗 (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \min\{\mathbf {b} \mathbf {y} \mid \mathbf {y} \mathbf {A} =\mathbf {c} ,\mathbf {y} \geq \mathbf {0} \}\,} が, 整数の最適解 $\mathbf {y} ^{*}\,$ をもつならば, 全双対整数的 (totally dual integral, TDI) であるという.