[Fwd: Linear Program Optimal Extreme Points]

[Andrew Makhorin]

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