Re: [Fwd: Linear Program Optimal Extreme Points]

[Naszvadi Peter]

Hi,

A finite dimensional polyhedron could have exponentially many vertices! 
For an all-zero objective function - in case when the LP problem turns 
to a feasibility problem: no one can check nor list all the vertices in 
polynomial time = no polynomial size witness, can't be NP-complete!
Even more difficult problem.

Regards,
NASZVADI, Peter

2022-10-06 15:18 időpontban Manuel Muñoz Márquez ezt írta:
> Hi, Andrew:
>
> I don't kown if it is implemented somewhere. But the problem of
> generating all the optimal vertices is the same as generating all the
> vertices of a new polyhedron in 1 lower dimension.
>
> But that problem is known to be NP-complete [1], so it is very hard or
> almost impossible as soon as the dimension increases.
>
> Furthermore, if I understand your procedure correctly, that way you
> only will find vertices next to the original. For simplicity, lets us
> assume that the optimal polyhedron is a square. If the solver gives
> you the bottom left corner, you will only be able to find the bottom
> right and top left corners, but you will never reach the top right 
> corner.
>
> What is it your goal?
>
> Regards, Manuel.
>
> [1] https://link.springer.com/article/10.1007/s00454-008-9050-5
>
> El jue, 06-10-2022 a las 13:49 +0300, Andrew Makhorin escribió:
> > -------- Forwarded Message --------
> > From: Prabhu Manyem <prabhu.manyem@gmail.com>
> > To: fukuda@math.ethz.ch, Andrew Makhorin <mao@gnu.org>, 
> > avis@cs.mcgill.c
> > a
> > Subject: Linear Program Optimal Extreme Points
> > Date: Thu, 6 Oct 2022 10:04:22 +1030
> >
> > Dear Andrew, Komei, David,
> >
> > I am a retired Maths professor in Adelaide, Australia.
> >
> > About the problem of enumerating all OEP (optimal extreme points) for
> > a Linear Program, I tried the following approach, using GLPK
> > software.. Is this a good way to handle degeneracy?  Please let me
> > know.
> >
> > For my instances, I have explicitly added lower bound constraints of 
> > the
> > form
> > "x_i >= 0"  for each variable x_i..
> >
> > (1) Solve the original Linear Program (call this LP0).. This returned
> > an optimal solution value of 50 (for my example).
> > The objective function is  "Max. Z = CX"... So  Z_{max} = 50.
> >
> > (2) Now add the constraint  "CX = 50" to the original LP.. This gives
> > us a new LP, which we can call LP1... Solve  LP1.. With GLPK, I was
> > able to save the last BFS (basic feasible solution) of LP1 to a file,
> > say Soln-1.bas (using the  "-w Soln-1.bas"  option).
> > Soln-1.bas  is the first OEP (optimal extreme point).
> >
> > (3) In Soln-1.bas, find the lexicographically first Non-Basic
> > variable.. For example, let us say that this is x5... Since I want to
> > avoid degeneracy and go to a new OEP,  I modify the Lower Bound for
> > x5... I modify  "x5 >= 0"  to  "x5 >= epsilon"  where epsilon is a
> > very small positive number.. Call this LP2.
> >
> > (4) Now run LP2 using GLPK, using the previous basis Soln-1.bas as the
> > starting solution.. In GLPK, you can do this using the "--ini
> > Soln-1.bas" option in the terminal command line... The LP2 output
> > should be written to "Soln-2.bas".
> >
> > (5) If Step 4 is a failure, that is, LP2 is infeasible, then check
> > Soln-1.bas, and find the NON-BASIC variable lexicographically next to
> > x5, for example, x8... Then the lower bound "x5 >= epsilon" should be
> > reset to zero ("x5 >= 0),  and the lower bound for x8 should be set to
> > epsilon (x8 >= epsilon)... Now run this new LP, again using the
> > "--ini Soln-1.bas"  option in GLPK.
> >
> > On the other hand, if Step 4 is a success (that is, LP2 is feasible),
> > then Soln-2 is the second OEP.
> > Then we do something similar to Step 3... Open Soln-2.bas, find the
> > lexicographically smallest Non-basic variable, for example, x9, reset
> > the lower bound of x5 to zero (x5 >= 0), change the lower bound of x9
> > to epsilon (x9 >= epsilon), and the solve the new LP (call it LP3) in
> > GLPK using the  "--ini Soln-2.bas"  option.
> >
> > We traverse the OEP's in a tree-like fashion..
> >
> > I assume that the above approach  (setting a Non-basic variable to >=
> > epsilon and solving a new LP, using the last BFS of the previous LP as
> > a starting point for the new LP)  is NOT a new idea... But I would
> > like to know if this has been implemented.
> >
> > Look forward to your comments and suggestions.. Thank you.. (And
> > thanks to Andrew for GLPK).
> >
> > -Prabhu
> >
> > Dr Prabhu Manyem
> > Retired Professor of Applied Mathematics
> > Nanchang Institute of Technology
> > Currently in Adelaide, Australia