<p>Here is an instance that could be <em>close</em> to a counterexample to the
claim.</p>

<p>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</p>

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

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

<p>In summary, the LP $P'$ has <em>an</em> 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.</p>

CC BY-SA 3.0
2012-07-18T01:28:10.290Z
Thanks! That does work! How did you come up with this example? Is there a class of problems from which it is drawn?
Ankur
CC BY-SA 3.0
2012-08-08T20:56:35.787Z
The matrix is a modification of the boundary matrix of a Mobius strip, given in [our paper](http://arxiv.org/abs/1001.0338) on optimal homologous cycles. I've been playing around with such boundary matrices recently, and hence somewhat naturally started with this matrix to create the example I gave.
kbala
CC BY-SA 3.0
2012-07-14T02:10:55.790Z
2012-07-14T02:10:55.790Z
kbala
<p>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.</p>

<p>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?</p>

<p>I would appreciate any counter-examples or pointers..</p>

CC BY-SA 3.0
2012-07-06T04:53:57.353Z
@Kaveh not sure that approximation-algorithms is the right tag here. or even ds.algorithms
Suresh Venkat
CC BY-SA 3.0
2012-07-06T14:44:01.963Z
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.
Chandra Chekuri
CC BY-SA 3.0
2012-07-06T17:26:12.427Z
@Suresh, doesn't linear programming and optimization fall in algorithms?
Kaveh
CC BY-SA 3.0
2012-07-06T19:00:57.430Z
@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!
Ankur
CC BY-SA 3.0
2012-07-07T17:40:07.217Z
This particular question is closer to the tags that it currently has.
Suresh Venkat
CC BY-SA 3.0
2012-07-07T21:05:24.917Z
@Suresh, I didn't say we should remove the other ones.
Kaveh
CC BY-SA 3.0
2012-07-07T22:28:15.060Z
Sure. But ds.algorithms seemed  overly broad and even cc.complexity might have worked. This is really math.optimization
Suresh Venkat
CC BY-SA 3.0
2012-07-20T19:51:03.600Z
Why was the set-cover tag removed?
Kristoffer Arnsfelt Hansen
CC BY-SA 3.0
2017-09-18T15:25:16.193Z
_"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')."_  Careful, this is not true. An LP can have integrality gap zero, without the dual having optimal integer solutions.  E.g. consider the standard shortest s-t path LP (1 unit min-cost s-t flow), or min s-t cut LP (in graphs with non-integer weights/capacities).  (These LPs are also counter-examples to the question in your post.)
Neal Young
<ds.algorithms><optimization><linear-programming><integrality-gap>
Does zero integrality gap imply zero duality gap for certain problems?
Ankur
# Does zero integrality gap imply zero duality gap for certain problems?

(Asked by: username_0 on 2012-07-06)

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

**Tags:** ds.algorithms, optimization, linear-programming, integrality-gap
> **Comments:**
> **username_1**: @Kaveh not sure that approximation-algorithms is the right tag here. or even ds.algorithms  
> **username_2**: 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.  
> **username_3**: @Suresh, doesn't linear programming and optimization fall in algorithms?  
> **username_0**: @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!  
> **username_1**: This particular question is closer to the tags that it currently has.  
> **username_3**: @Suresh, I didn't say we should remove the other ones.  
> **username_1**: Sure. But ds.algorithms seemed  overly broad and even cc.complexity might have worked. This is really math.optimization  
> **username_4**: Why was the set-cover tag removed?  
> **username_5**: _"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')."_  Careful, this is not true. An LP can have integrality gap zero, without the dual having optimal integer solutions.  E.g. consider the standard shortest s-t path LP (1 unit min-cost s-t flow), or min s-t cut LP (in graphs with non-integer weights/capacities).  (These LPs are also counter-examples to the question in your post.)  

---

## 1 answers

### Answer by username_6 on 2012-07-14. Score: 5 | Accepted answer

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.

> **Comments:**
> **username_0**: Thanks! That does work! How did you come up with this example? Is there a class of problems from which it is drawn?  
> **username_6**: The matrix is a modification of the boundary matrix of a Mobius strip, given in [our paper](http://arxiv.org/abs/1001.0338) on optimal homologous cycles. I've been playing around with such boundary matrices recently, and hence somewhat naturally started with this matrix to create the example I gave.  

---

