-------- Forwarded Message --------
From: Prabhu Manyem <prabhu.man...@gmail.com>
To: fuk...@math.ethz.ch, Andrew Makhorin <m...@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