Why there isn't lexicographically smallest solution to a bounded linear program?

Question

I am learning computational geometry when I run into this confusion. "A bounded 2D linear program may not have a lexicographically smallest solution", as the book says. I wonder why? I think we can always choose an "optimal vertex" from the feasible region based on either x-coordinates or y-coordinates.

Can anyone provide an example where a 2D LP that is bounded, but no lexicographically smallest solution?

Thanks

Answer 1

Consider the linear programming problem

minimize $y$ subject to $y \ge 0$, $y \le 1$, $x \le 0$

where there are optimal solutions $(x, 0)$ for $-\infty < x \le 0$. The point is that although the problem is bounded, the feasible region is not.