Apakah zero integrality gap menyiratkan zero duality gap untuk masalah tertentu?

Kita tahu bahwa jika kesenjangan antara nilai-nilai program integer dan dual-nya ("kesenjangan kualitas") adalah nol, maka relaksasi pemrograman linier dari program integer dan dual relaksasi, keduanya mengakui solusi integral (integral nol) celah"). Saya ingin tahu apakah kebalikannya berlaku, setidaknya dalam beberapa kasus.

A 0 - 1 P ′ P P $P: \max\{1^Tx: Ax \leq 1, x\in \{0,1\}^n\}$$A$$0-1$$P'$$P$$P'$

Saya akan menghargai contoh atau petunjuk balasan apa pun ..

Berikut ini adalah contoh yang bisa dekat dengan contoh berlawanan dengan klaim.

Pertimbangkan LP dan dual P ′ = min { 1 T y + 1 T z | A T y + z ≥ 1 , y ≥ 0 , z ≥ 0 } untukmatriks 12 × $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$