14
$\begingroup$

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

$\endgroup$
  • $\begingroup$ @Kaveh not sure that approximation-algorithms is the right tag here. or even ds.algorithms $\endgroup$ – Suresh Venkat Jul 6 '12 at 4:53
  • 4
    $\begingroup$ 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. $\endgroup$ – Chandra Chekuri Jul 6 '12 at 14:44
  • $\begingroup$ @Suresh, doesn't linear programming and optimization fall in algorithms? $\endgroup$ – Kaveh Jul 6 '12 at 17:26
  • $\begingroup$ @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! $\endgroup$ – Ankur Jul 6 '12 at 19:00
  • $\begingroup$ This particular question is closer to the tags that it currently has. $\endgroup$ – Suresh Venkat Jul 7 '12 at 17:40
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks! That does work! How did you come up with this example? Is there a class of problems from which it is drawn? $\endgroup$ – Ankur Jul 18 '12 at 1:28
  • 1
    $\begingroup$ The matrix is a modification of the boundary matrix of a Mobius strip, given in our paper 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. $\endgroup$ – kbala Aug 8 '12 at 20:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.