Un écart d'intégralité nul implique-t-il un écart de dualité nul pour certains problèmes?

Nous savons que si l'écart entre les valeurs d'un programme entier et son dual (le "gap de dualité") est nul, alors les relaxations de programmation linéaire du programme entier et le dual de la relaxation admettent toutes deux des solutions intégrales (intégrité nulle) écart"). Je veux savoir si l'inverse tient, du moins dans certains cas.

Supposons que j'ai un programme entier 0-1 , où la matrice A est une matrice 0-1 . Supposons que la relaxation de programmation linéaire P ' de P ait une solution optimale intégrale. Alors la programmation linéaire dual de P ' admet-elle aussi une solution intégrale?A 0 - 1 P ′ P P $P: \max\{1^Tx: Ax \leq 1, x\in \{0,1\}^n\}$$A$$0-1$$P'$$P$$P'$

J'apprécierais tous les contre-exemples ou pointeurs ..

Voici une instance qui pourrait être proche d'un contre-exemple de la revendication.

Considérons le LP et son double pour la matriceP ′ = 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}\,.$

Une solution optimale de est donnée par (toutes les autres variables sont nulles), avec la valeur de la fonction objectif de . La solution optimale de est donnée par le vecteur . Si vous résolvez tant que programme entier, la valeur optimale de la fonction objectif n'est que de et est une solution optimale.$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]$

En résumé, le LP a une solution optimale intégrale, mais son dual, n'a pas de solution optimale intégrale. Les rôles primal-dual sont inversés par rapport à la configuration souhaitée par Ankur. Mais compte tenu de la nature de la dualité LP, cette instance pourrait toujours être considérée comme un contre-exemple de l'énoncé général de la revendication initiale.$P'$$P$