# Estimation of the number of optimum vertices

Consider any linear programming model of $$n$$ variables and $$m$$ constraints which has multiple optimum solutions. If it is possible, I'd like to know the lower and upper limits (in terms of $$n$$, $$m$$ and possibly other elements as well) for the number of vertices from the feasible polyhedron that belongs to the set of optimum solutions.

I came to believe, that as long as the feasible polyhedron contains more than a single point, there would be at least 2 different vertices that belong to the set of optimum solutions. However, for the upper limit, I have no clue, except that the total number of vertices in a feasible polyhedron (which are not necessarily optimum) is at most $$2^n$$.

I'm not sure if my thoughts on this subject are correct, and maybe it's not possible to have a good estimation at all on this matter.

Your belief that there will be two different vertices in the set of optimal solutions as long as the feasible polyhedron contains more than a single point is incorrect. In practice, most LPs have unique solutions. As far as an upper bound on the number of optimal vertices, let's assume that you have $$m$$ constraints including sign restrictions on the variables. For simplicity, let's also assume that $$m>n$$ (which need not be the case if you have sign-unrestricted variables). Since a vertex is the intersection of $$n$$ affinely independent constraint hyperplanes, in the worst case you would have $$\binom{m}{n}$$ vertices, all of which would be optimal if the objective function were constant. Under the given assumptions, that bound is valid, but I don't know that it is "good" if "good" means useful.