Does zero integrality gap imply zero duality gap for certain problems? We know that if the gap between the values of an integer program and its dual (the "duality gap") is zero, then the linear programming relaxations of the integer program and the dual of the relaxation, both admit integral solutions (zero "integrality gap"). I want to know if the converse holds, at least in some cases.

Suppose I have a 0-1 integer program $P: \max\{1^Tx: Ax \leq 1, x\in \{0,1\}^n\}$, where the matrix $A$ is a $0-1$ matrix. Suppose the linear programming relaxation $P'$ of $P$ has an integral optimal solution. Then does the linear programming dual of $P'$ also admit an integral solution?

I would appreciate any counter-examples or pointers..
Here is an instance that could be close to a counterexample to the
claim.

Consider the LP $P = \max \{ 1^T x \,|\, Ax \leq 1, x \leq 1, x \geq
0\}$ and its dual $P' = \min \{1^Ty + 1^Tz ~|~ A^Ty + z \geq 1, ~y
\geq 0, z \geq 0 \}$ for the $12 \times 6$ matrix

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

An optimal solution of $P'$ is given by $y_1=y_2=y_{12}=1$ (all other
variables are zero), with the objective function value of $3$. The
Optimal solution of $P$ is given by the vector $x =
[0.5~0.5~0~1~0.5~0.5]^T$. If you solve $P$ as an integer program, the
optimal objective function value is only $2$, and $x = [1~0~0~1~0~0]$
is an optimal solution.

In summary, the LP $P'$ has an integral optimal solution, but its
dual, $P$ does not have an integral optimal solution. The primal-dual
roles are reversed from the set up that Ankur wanted. But given the
nature of LP duality, this instance could still be considered a
counterexample to the general statement of the original claim.