# Equivalence of a binary linear program and its relaxation

We know that given a binary (0-1) linear program, we can find lower/upper bounds using its relaxation. But, there are instances (such as shortest path problem with non-negative cycles, bipartite matching, max-flow, etc) for which the feasible region of the relaxation actually has integral vertices. My question is about the methods we can use to prove this property for a given problem that we know for which this property holds. Is there a machinery for this or it is something creative and problem-based?

Update: Assume matrix $A$ is given as

 [1 1 0 1 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0]
[1 1 1 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0]
[1 0 1 1 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0]
[0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0]
[0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0]
[0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0]
[0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0]
[0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0]
[0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1]


I tested this matrix by Matlab, and it is not TU. Given $d_n$, $n =1,\ldots,9$, the problem is

\begin{align} \min \quad &\sum_{n=1}^{22} b_n c_n \\ s.t. \quad& A \begin{bmatrix} b_1 \\ \vdots \\ b_{22} \end{bmatrix}_{22 \times1} = \begin{bmatrix} 1 \\ \vdots \\ 1 \end{bmatrix}_{9 \times1}\\ & b_n \in \{0,1\}, \quad n=1,\ldots,22. \end{align} and its relaxation is: \begin{align} \min \quad &\sum_{n=1}^{22} b_n c_n \\ s.t. \quad& A \begin{bmatrix} b_1 \\ \vdots \\ b_{22} \end{bmatrix}_{22 \times1} = \begin{bmatrix} 1 \\ \vdots \\ 1 \end{bmatrix}_{9 \times1}\\ & b_n \geq 0, \quad n=1,\ldots,22. \end{align} where \begin{align} c_n = \max\{A[1,n]*d_1,A[2,n]*d_2,\ldots, A[9,n]*d_9 \}. \end{align} For example, $c_1 = \max\{d_1,d_2,d_3\}$ and $c_3 = \max\{d_2,d_3\}$.

What can we do to show this: "The vertices of the polytope of the relaxation problem are integral"?

Then, instead of solving the IP, we can solve its LP relaxation.

• I don't see how you can "use duality to show the equivalence". There is no duality for optimization problems with integers. – LinAlg Nov 19 '16 at 10:33
• @LinAlg It is not true that there is no "duality for optimization problems with integers". Given a problem P, by definition a dual probleml D for P is a problem that bounds P. If P is linear then D is the ordinary linear Dual, and strong duality holds (no duality gap). For an integer problem, the linear relaxation is the easiest way to obtain a Dual; anather dual problem can be obtained by the Lagrangian relaxation. – Marcello Sammarra Nov 19 '16 at 12:58
• I haven't ever seen anyone call the linear relaxation a dual problem. Typically one talks about Lagrange/Wolfe/Fenchel duality. None of those concepts is of any use when integers come into play, which is why noone studies them. My point was that the statement that one can "use duality to show the equivalence" is incomprehensible. – LinAlg Nov 19 '16 at 14:11
• @LinAlg There is a way to show this by duality. I should have said the duality of the relaxed LP. We can find the dual of the relaxed LP for this problem and solve it. The solution is a lower bound for the relaxed LP (primal) and this value is achieved by an integral solution. Hence, we can say that the integral solution is optimal for the LP and the original IP and its LP relaxation are equivalent. But, the application of this method is limited. – m0_as Nov 19 '16 at 18:19
• That's not really using duality, as you could have simply solved the relaxed LP itself (whose value equals the value of the dual of the relaxed LP). – LinAlg Nov 19 '16 at 20:36

In the example in your initial question, the coefficient matrix is $\begin{pmatrix}1 & 1 \\ 1 & 1\end{pmatrix}$. The determinant of this matrix is $0$ while all submatrices have determinant $1$. So, this constraint matrix is TUM. Since the right hand side is integral, any basic feasible solution is integral too.
In the example in your updated question, it is merely luck that your solution is integral. If I solve it with a different objective function, I obtain a fractional solution: take $d_n=1$ for $n\in\{2,4,9\}$, $d_n=0$ otherwise. Then $c_n=1$ for $n \in\{1,2,3,7,8,11,13,15,17,22\}$, $c_n=0$ otherwise. When you use the variables $b_n$ for $n$ in $\{4,5,6,7,8,10,11,12,13\}$ as a basis in the simplex method, you obtain a fractional solution that is optimal. There are integral optimal solutions, but this fractional one proves that the relaxation is not equivalent to the original problem.
• No, I don't think so. Now, $d$ is a vector of size 9 but $c$ was a vector of size 22. I just check it with $d=[1,1,1,0,0,0,0,0,0]$, they are equivalent. – m0_as Nov 19 '16 at 22:31
• How do you solve this problem? The $c$ you mentioned is correct but I solved this and the solution is $b_1=b_{17}=b_{18}=b_{19}=b_{20}=b_{21}=b_{22}=1$ and other $b_i$'s are zero and the optimal value is 1! – m0_as Nov 19 '16 at 22:54