Can LP with bounded feasible region be converted to LP with unbounded feasible region after adding artificial variables?

Question

In Big-M method we add artificial variables to a linear programming problem(call it $p$) to convert it to a secondary problem(call it $p^\prime$) so we can find basic feasible solution to start Simplex algorithm.
Does there exist a linear programming problem with bounded feasible region which will have unbounded feasible region after adding artificial variables?

Answer 1

This holds true for all feasible bounded problems. A constraint $a^Tx \geq b$ with $b > 0$ becomes $a^Tx-s_i+ a_i = b$ with $s_i$ the slack variable and $a_i$ the excess variable. If $(x,s,a)$ is feasible, then $(x,s+\alpha,a+\alpha)$ is also feasible for any $\alpha>0$, so the new feasible region is unbounded.

Based on the comment it seems like you are interested in whether the projection of the feasible region of $p'$ onto the variables in $p$ is unbounded. That can also be the case, but not necessarily. As a simple example, consider the set $S_1=\{x\in\mathbb{R} : 1 \leq x \leq 2\}$. After adding slacks and an artificial variable, this becomes the set $S_2=\{(x,a,s_1,s_2) \in\mathbb{R}^4 : x-s_1+a=1, x+s_2=2\}$. The constraint $x \geq 1$ can be violated arbitrarily by increasing the value of $a$ (for example, $(0,1,0,2) \in S_2$), so the projection of $S_2$ onto $x$ is $x \leq 2$.