1

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.

RobPratt
  • 45,619
Serpent9006
  • 37
  • 3
    This is not generally true. What is the source of the statement? – RobPratt Sep 01 '20 at 16:18
  • 2
    Yeah, this sounds fishy in general. My guess is there is something special about the particular problem being discussed? – Zim Sep 01 '20 at 16:20
  • @Zim , I thought that it could be limited to this problem: https://math.stackexchange.com/questions/2904798/finding-the-requirement-space-and-feasibility-of-a-lp-problem However, I happened to hear this again from a senior student. It shouldn't be true in general, right? – Serpent9006 Sep 01 '20 at 16:25
  • 1
    I've never heard of a result like that before, so I'm very skeptical that it would be true. I feel like maximizing $\sum_{i=1}^N x_i$ over the unit cube should be a counterexample, right? – Zim Sep 01 '20 at 16:38

1 Answers1

2

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.

RobPratt
  • 45,619
Siong Thye Goh
  • 149,520
  • 20
  • 88
  • 149