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