4
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ I don't see how you can "use duality to show the equivalence". There is no duality for optimization problems with integers. $\endgroup$ – LinAlg Nov 19 '16 at 10:33
  • $\begingroup$ @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. $\endgroup$ – Marcello Sammarra Nov 19 '16 at 12:58
  • $\begingroup$ 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. $\endgroup$ – LinAlg Nov 19 '16 at 14:11
  • $\begingroup$ @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. $\endgroup$ – m0_as Nov 19 '16 at 18:19
  • $\begingroup$ 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). $\endgroup$ – LinAlg Nov 19 '16 at 20:36
2
$\begingroup$

Typically you show that the coefficient matrix is totally unimodular (TUM). Then by Cramer's rule any basic feasible solution is integral (if the right hand side is integral).

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.

$\endgroup$
22
  • $\begingroup$ Thanks. I know about this method. But, it doesn't work for my problem. $\endgroup$ – m0_as Nov 19 '16 at 19:11
  • $\begingroup$ Thanks for the counter-example. The problem I described wasn't exactly what I had. I tried to simplify it. I know you have already answered my question twice, but can you take a look at the updated version? For this one, I tried a lot of random input, the two problems are equivalent. $\endgroup$ – m0_as Nov 19 '16 at 22:21
  • $\begingroup$ 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. $\endgroup$ – m0_as Nov 19 '16 at 22:31
  • $\begingroup$ 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! $\endgroup$ – m0_as Nov 19 '16 at 22:54
  • $\begingroup$ @m0_as You are correct. I have updated my answer once more. Note that your solution shows some degeneracy (fewer than 9 b's are nonzero), so many solutions may be optimal. $\endgroup$ – LinAlg Nov 20 '16 at 11:12

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.