Show $Ax \leq b$ is Totally Dual Integral implies $Ax \leq b - Aw$ also TDI.

Question

Let $A \in \mathbb{R}^{m \times n}, b \in \mathbb{R}^{m}.$ Let $ Ax \leq b$ be Totally Dual Integral. Let $w \in \mathbb{R^n}$.

Prove that $Ax \leq b - Aw$ is also Totally Dual Integral.

Answer 1

We note that, we want to show that for any $c_1,c_2 \in \mathbb{Z}^n$, such that there is a feasible bounded solution to $$\max_{x,w}\{c_1^Tx+c_2^Tw:Ax+Aw\le b\}$$ that there is an integer optimal dual solution. We know that this problem has the dual $$\min_y\{b^Ty:A^Ty=c_1,A^Ty=c_2,y\ge0\}.$$ We note that this problem is infeasible if $c_1 \neq c_2.$ Since, dual infeasibility would imply primal unboundedness, we only have to concider the case where $c_1=c_2=c \in \mathbb{Z}^n$. But, then the problem reduces to the dual of the original problem i.e., $$\min_y\{b^Ty:A^Ty=c,y \ge 0\}.$$ Thus, the result follows from the original problem being TDI.