Re: [Fwd: Linear Program Optimal Extreme Points]

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 almo=
st impossible as soon as the dimension increases.

Furthermore, if I understand your procedure correctly, that way you only wi=
ll 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=C3=B3:
> -------- 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
>=20
> Dear Andrew, Komei, David,
>=20
> I am a retired Maths professor in Adelaide, Australia.
>=20
> 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?=C2=A0=C2=A0Please let=
 me
> know.
>=20
> For my instances, I have explicitly added lower bound constraints of the
> form
> "x_i >=3D 0"=C2=A0=C2=A0for each variable x_i..
>=20
> (1) Solve the original Linear Program (call this LP0).. This returned
> an optimal solution value of 50 (for my example).
> The objective function is=C2=A0=C2=A0"Max. Z =3D CX"... So=C2=A0=C2=A0Z_{=
max} =3D 50.
>=20
> (2) Now add the constraint=C2=A0=C2=A0"CX =3D 50" to the original LP.. Th=
is gives
> us a new LP, which we can call LP1... Solve=C2=A0=C2=A0LP1.. With GLPK, I=
 was
> able to save the last BFS (basic feasible solution) of LP1 to a file,
> say Soln-1.bas (using the=C2=A0=C2=A0"-w Soln-1.bas"=C2=A0=C2=A0option).
> Soln-1.bas=C2=A0=C2=A0is the first OEP (optimal extreme point).
>=20
> (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,=C2=A0=C2=A0I modify the Lower Bound=
 for
> x5... I modify=C2=A0=C2=A0"x5 >=3D 0"=C2=A0=C2=A0to=C2=A0=C2=A0"x5 >=3D e=
psilon"=C2=A0=C2=A0where epsilon is a
> very small positive number.. Call this LP2.
>=20
> (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".
>=20
> (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 >=3D epsilon" should be
> reset to zero ("x5 >=3D 0),=C2=A0=C2=A0and the lower bound for x8 should =
be set to
> epsilon (x8 >=3D epsilon)... Now run this new LP, again using the
> "--ini Soln-1.bas"=C2=A0=C2=A0option in GLPK.
>=20
> 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 >=3D 0), change the lower bound of x9
> to epsilon (x9 >=3D epsilon), and the solve the new LP (call it LP3) in
> GLPK using the=C2=A0=C2=A0"--ini Soln-2.bas"=C2=A0=C2=A0option.
>=20
> We traverse the OEP's in a tree-like fashion..
>=20
> I assume that the above approach=C2=A0=C2=A0(setting a Non-basic variable=
 to >=3D
> epsilon and solving a new LP, using the last BFS of the previous LP as
> a starting point for the new LP)=C2=A0=C2=A0is NOT a new idea... But I wo=
uld
> like to know if this has been implemented.
>=20
> Look forward to your comments and suggestions.. Thank you.. (And
> thanks to Andrew for GLPK).
>=20
> -Prabhu
>=20
> Dr Prabhu Manyem
> Retired Professor of Applied Mathematics
> Nanchang Institute of Technology
> Currently in Adelaide, Australia
>=20
>=20