3
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
7
  • $\begingroup$ What do you mean by "most LPs have unique solutions" ? $\endgroup$
    – G Oliveira
    May 16, 2020 at 17:52
  • $\begingroup$ If I knew all vertices in the optimum solution of a given LP, from there, doesn't it make sense to try finding the hyperplane which intersects all opt solutions ? $\endgroup$
    – G Oliveira
    May 16, 2020 at 17:57
  • $\begingroup$ Still regarding my last comment, I am interested in drafting optimum solution samples, which would be done by means of such hyperplane, as long as I am capable drafting only from the feasible region. $\endgroup$
    – G Oliveira
    May 16, 2020 at 18:05
  • 3
    $\begingroup$ Isn't finding an optimal hyperplane trivial for any non-trivial objective? Just use "objective function = optimal value". $\endgroup$
    – T_O
    May 16, 2020 at 18:35
  • 1
    $\begingroup$ @GOliveira In practice, problems with multiple optima are not uncommon, but problems with a single optimum are common and (I think) cover the majority of cases. Take a look at a sample of textbook problems and see how many have unique optima. $\endgroup$
    – prubin ♦
    May 17, 2020 at 18:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.