Justification of the big M method Given a LP we can solve it using the so called "big M method". I was curious about how this constant $M$ is determined and quickly enough ran into this. It is said that $M$ is large enough, so that must mean determining it from the input parameters is an open problem.
Still, I'd expect its existence is justified. More specifically, if we have a fixed LP $$\max\{c\cdot x \mid Ax = b, x\geq 0\} $$
then there should exist $M^*$ "large enough" such that for every $M > M^*$, all entries corresponding to the artificial variables of an optimal solution to the augmented problem vanish (yielding an optimal solution to the unaugmented problem). Any clues where this question might be addressed?
 A: Theoretically you can use revised simplex to determine a lower bound on $M$. You want $M$ to be large enough so that as long as an auxiliary variable is in the basis, it has a negative component in the first row simplex tableau. Let me assume $b\geq 0$ as otherwise you can multiply the constraint by $-1$. The big-M method solves
$$\max_{x,y}\{ c^Tx - M e^Ty : Ax+y=b, x\geq 0, y\geq 0\},$$
which can be reparameterized as:
$$\max_{x,y}\left\{ \begin{pmatrix}c\\-Me\end{pmatrix}^T \begin{pmatrix}x\\y\end{pmatrix} : \begin{pmatrix}A & I\end{pmatrix}\begin{pmatrix}x\\y\end{pmatrix}=b, \begin{pmatrix}x\\y\end{pmatrix}\geq 0\right\}.$$
An initial basic feasible solution is $x=0$, $y=b$. Let $B$ be the basic columns of the optimal solution and $N$ be the nonbasic columns, and let $c_B$ and $c_N$ be the coefficients in the objective function corresponding to the basic and nonbasic variables. The reduced cost vector is $c_B B^{-1}N-c_N$. The criterion for $M$ is that you should not have $c_B B^{-1}N-c_N\geq 0$ whenever $M$ is in $B$. You can simply take all possible combinations of $m$ linearly independent columns of $\begin{pmatrix}A & I\end{pmatrix}$ that contain at least one column that corresponds with $y$, compute $c_B B^{-1}N-c_N$, and thus derive the strongest lower bound on $M$. This is not practical however, since the number of combinations is quite large. It would be faster to just consider all possible basis vectors of the original problem and see which one is optimal.
Practically you can just use the two phase method or dual simplex to avoid the big-M method.
