Model formulation: a conclusion about the model before solving it

Question

I have found this simple model in a paper discussing robust optimization [1]

$$\max \vec{c}^{T}\vec{x}$$

s.t. $$\sum_j a_{ij}x_j + \sum_j \tilde{a}_{ij}y_j \leq b_i \;\;\;\forall i$$

$$ -y_j \leq x_j\leq y_j \;\;\;\forall j$$

$$\vec{l} \leq \vec{x} \leq \vec{u} $$

$$\vec{y} \geq 0$$

$a_{ij}$ and $\tilde{a}_{ij}$ are such that they form an interval $[a_{ij}-\tilde{a}_{ij}, a_{ij}+\tilde{a}_{ij}]$ (but I don't know whether it is relevant to what follows).

Let $\vec{x}^{*}$ be the optimal solution. The authors state "At optimality, clearly, $y_j=|x_j^{*}|$". Unfortunately, I am not able to understand this conclusion. Would you please help me understand?

Thanks

[1] Bertsimas, Sim, 2004, The Price of Robustness. Operations Research

Answer 1

If the reformulated constraint $\sum_j a_{ij}x_j + \tilde{a}_{ij}|x_j| \leq b_i$ is binding at optimality, a proof is easy (there is simply no other $y_j$ that is feasible). The conclusion is erroneous otherwise (although the solution remains optimal if you let $y_j = |x_j|$).