I am trying to answer the following problem but with no success:
Let $c\in \mathbb{R}^n, b\in \mathbb{R}^m, \bar{A}\in \mathbb{R}^{m\times n}$ and $\Delta\in \mathbb{R}^{m\times n}_+$ be given. Additionally, let $B = \{A \in \mathbb{R}^{m\times n} : |A_{ij} - \bar{A}_{ij} | \leq \Delta_{ij} \; \forall i,j \}$. We call a vector $x\in \mathbb{R}^n$ a robust feasible solution to the uncertain problem if $Ax \leq b$ for all $A\in B$. Write an explicit LP that minimizes $c^T x$ over all robust feasible solutions, and whose number of variables and constraints is polynomial in $m, n$.
I'm not even sure what a good start to the problem would be. If anyone could suggest a path to solve this I would greatly appreciate it.
Study single rows of the constraints, and write each element as $\bar a_{ij} + \Delta_{ij}z_{ij}$ where $|z_{ij}|\leq 1$, leading to $\sum_j a_{ij}x_j + \sum_j \Delta_{ij}z_{ij}x_j \leq b_i$. Can you see what the worst-case $z$ is and take it from there?