Re: [Fwd: Linear Program Optimal Extreme Points]

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 <[email protected]>
>> To: [email protected], Andrew Makhorin <[email protected]>, 
>> [email protected]
>> 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
>> 
>>