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

• @Kaveh not sure that approximation-algorithms is the right tag here. or even ds.algorithms Jul 6 '12 at 4:53
• In the first para what do you mean by dual of an integer program? It is useful to look at Schrijver's book on linear and integer programming to understand the basics of polyhedral theory and in particular when the linear programming relaxations have integer vertices. TUM matrices and TDI systems of inequalities are relevant to your question. Jul 6 '12 at 14:44
• @Suresh, doesn't linear programming and optimization fall in algorithms? Jul 6 '12 at 17:26
• @ChandraChekuri I am talking of integer linear programs; so the dual is the standard dual of an ILP for which weak duality holds. The difficulty here is that sufficient conditions for integrality of (primal) LP solutions (such as TUM/balanced etc) seem to pass through the seemingly stronger concept of integrality of solutions of the primal and its dual LP. This made me wonder if the integrality of the primal solution implies the integrality of the dual solution, at least for integral coefficients. PS: I could just walk to Siebel and we could talk there! I was in your class some years ago! Jul 6 '12 at 19:00
• This particular question is closer to the tags that it currently has. Jul 7 '12 at 17:40

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.