Czy zerowa luka integralności oznacza zerową lukę dualności dla niektórych problemów?

Wiemy, że jeśli różnica między wartościami programu liczb całkowitych i jego dualności („dualność”) wynosi zero, wówczas liniowe relaksacje programowania programu liczb całkowitych i dualność relaksacji dopuszczają rozwiązania integralne (integralność zerowa) luka"). Chcę wiedzieć, czy konwersacja się utrzymuje, przynajmniej w niektórych przypadkach.

Załóżmy, że mam program liczb całkowitych 0-1 , gdzie macierz jest macierzą . Załóżmy, że programowanie liniowe relaks z ma integralną rozwiązanie optymalne. Czy zatem dualne programowanie liniowe również dopuszcza integralne rozwiązanie?$P: \max\{1^Tx: Ax \leq 1, x\in \{0,1\}^n\}$$A$$0-1$$P'$$P$$P'$

Byłbym wdzięczny za wszelkie kontrprzykłady lub wskazówki ...

Oto przykład, który może być zbliżony do kontrprzykładu do roszczenia.

Rozważ LP $P = \max \{ 1^T x \,|\, Ax \leq 1, x \leq 1, x \geq 0\}$$P' = \min \{1^Ty + 1^Tz ~|~ A^Ty + z \geq 1, ~y \geq 0, z \geq 0 \}$$12 \times 6$

$A = \begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 1\\ 0 & 1 & 0 & 0 & 1 & 0\\ 1 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 1 & 1\\ 0 & 1 & 0 & 0 & 0 & 0\\ 1 & 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0 & 0 & 0\\ 1 & 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1 & 0 & 0\\ 0 & 1 & 1 & 0 & 0 & 1\\ 0 & 0 & 1 & 1 & 0 & 0 \end{bmatrix}\,.$

$P'$$y_1=y_2=y_{12}=1$$3$$P$$x = [0.5~0.5~0~1~0.5~0.5]^T$$P$$2$$x = [1~0~0~1~0~0]$

$P'$$P$