Означает ли разрыв нулевой целостности нулевой разрыв двойственности для определенных задач?

Мы знаем, что если разрыв между значениями целочисленной программы и ее двойственной («двойственность разрыв») равен нулю, то линейные программные релаксации целочисленной программы и двойственной релаксации, оба допускают интегральные решения (нулевая) интегральность разрыв "). Я хочу знать, верно ли обратное, по крайней мере, в некоторых случаях.

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

Буду признателен за любые контрпримеры или указатели ..

Вот пример, который может быть близок к контрпримеру к иску.

Рассмотрим LP и его двойственное P ′ = min { 1 T y + 1 T z | A T y + z ≥ 1 , y ≥ 0 , z ≥ 0 } дляматрицы 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}\,.$

Оптимальное решение дается выражением y 1 = y 2 = y 12 = 1 (все остальные переменные равны нулю) со значением целевой функции 3 . Оптимальное решение P задается вектором х = [ 0,5 0,5 0 1 0,5 0,5 ] T . Если вы решите P как целочисленную программу, оптимальное значение целевой функции будет только 2 , а x = [ 1 0 0 1 $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$