全双対整数性

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

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