0

I need to show that $Ax\leq b$ for $A=\begin{pmatrix} 1 & -1\\ 1 & 1\end{pmatrix}$ and $b=(0, 0)^T$ is not total dual integral. So I have calculated that $Ax\leq b$ holds only when $x_1\leq 0$ and $x_1\leq x_2\leq -x_1$.I consider $A^Ty=c$ for $y\geq0$ and got the result $y_1=\frac{c_2-c_1}{2}$ and $y_2=\frac{c_1+c_2}{2}$. Because $y\geq0$, we must have $c_2\geq0$ und $-c_2\leq c_1\leq c_2$. Now we have $\max c^Tx\leq c_1x_1+c_2x_2=(c_1+c_2)x_1$. It seems there is no finite solution for $\max c^Tx$. So how can we see that $Ax\leq b$ is not TDI? Thanks in advance for any hints!

toki
  • 95

0 Answers0