Is there a way to find the optimal point with this special property in polynomial time? Note that the polytope in the linear program may be unbounded.
Asked
Active
Viewed 85 times
1 Answers
0
Suppose minimization.
- Solve the original LP problem, yielding optimal objective value $z^*$.
- Introduce an objective cut $z \le z^*$.
- Solve the new LP problem with the objective of maximizing the specified variable $x_j$.
LP is polynomial, and the process above involves solving two LPs of essentially the same size.
RobPratt
- 45,619
-
Unfortunately, this will not work as the new LP can be unbounded. Is there a way to limit the search only to the vertices? – Zing Jun 11 '22 at 08:05
-
OK, I see that my suggestion can fail in the unbounded case, even with two variables: minimize $-x_1$ subject to $0\le x_1\le 1$ and $x_2\ge 0$, and then you want to maximize $x_2$ subject to $x_1=1$ and $x_2\ge 0$, which is unbounded. But if you also restrict to the only extreme point $(1,0)$, the problem is bounded. – RobPratt Jun 11 '22 at 13:55