完全な二重の完全性

数学的最適化において、全双対整数は多面体の整数性の十分条件です。したがって、そのような多面体の整数点上の線形目的関数の最適化は、線形計画法の手法を使用して行うことができます。

およびが有理数である線形システム は、任意の に対して線形計画の実行可能な有界解が存在する とき、全双対積分 (TDI) と呼ばれます。${\displaystyle Ax\leq b}$${\displaystyle A}$${\displaystyle b}$${\displaystyle c\in \mathbb {Z} ^{n}}$

${\displaystyle {\begin{aligned}&&\max c^{\mathrm {T} }x\\&&Ax\leq b,\end{aligned}}}$

整数最適双対解が存在する。^{[1] [2] [3]}

Edmonds と Giles ^{[2] は}、多面体がTDI システム の解集合であり、 がすべて整数要素である場合、 のすべての頂点は整数値であることを示しました。したがって、上記のような線形計画法を単体アルゴリズムで解くと、返される最適解は整数になります。さらに、Giles と Pulleyblank ^[1]は、がすべての頂点が整数値である多面体である場合、 は何らかの TDI システム の解集合であり、が整数値であることを示しました。 ${\displaystyle P}$${\displaystyle Ax\leq b}$${\displaystyle b}$${\displaystyle P}$${\displaystyle P}$${\displaystyle P}$${\displaystyle Ax\leq b}$${\displaystyle b}$

TDIは全ユニモジュラ性よりも整数性に対する十分条件としては弱いことに注意されたい。^[4]