LP problem with more than 2 decision variables
Consider a Linear Programming problem with more than 2 decision variables. I came across a statement that - an optimal solution can be obtained by creating sub-problems with utmost 2 decision variables (while setting the remaining decision variables to $0$) and selecting the optimum among all such sub-problems.
This is one approach for solving an LP problem. But how is the optimum solution from these sub-problems same as the global optimum of the original problem? I find it difficult to believe that only two decision variables can generate the global optimal solution.
$\endgroup$ 41 Answer
$\begingroup$Clearly it is not true.
To construct a counterexample, consider the case where none of the elements of the feasible region take $0$ values.
E.g. $\min x+y+z$ subject to $x \ge 1, y \ge 1, z \ge 1$.
For the post that is linked notice that it is of the form of
$$\min c^Tx$$
subject to $Ax \ge b, x \ge 0$
where $A$ consists of $2$ rows. We know that for linear programming, if an optimal solution exists, it occurs at a basic feasible solution. Since there are $4$ variables, $4$ of the constraints must be active at a BFS, of which at least $2$ are from the sign constraints.
$\endgroup$
