Re: [Fwd: Linear Program Optimal Extreme Points]

[Manuel Muñoz Márquez]

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
> 
>