Does zero integrality gap imply zero duality gap for certain problems?

Question

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..

Answer 1

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 & 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}\,. $

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.