Linprog Incorrect Outputs

[alberthli]

The Problem

The output of linprog_simplex is not correct. Specifically,

1. The output of linprog_simplex in QuantEcon is not deterministic. On subsequent runs, the optimal value changes unpredictably.
2. Due to this, the outputs also do not match those from scipy.

Reproducing the Error

Here are the files containing a minimal reproducible example comparing the optimal value to that obtained using scipy: mre.zip. I've zipped up 16 fixed linear programs from my use case along with a script that solves each of them using QuantEcon and scipy.

The dependencies and their versions in the MRE are

numpy==1.24.3
quantecon==0.7.1
scipy==1.10.1

In the attached files, the optimal values of 16 LPs from scipy are consistently given by

[
    0.3417887779985447, 0.3092034723662913, 0.36648408453360626, 0.2899030041327701,
    0.4298323340643794, 0.3078721435150979, 0.4117489369285151, 0.299359203576592,
    0.34178877799854457, 0.28990300413277015, 0.3664840845336063, 0.3092034723662913,
    0.4298323340643799, 0.29935920357659196, 0.4117489369285152, 0.3078721435150978,
]

However, when using QuantEcon, here are two example outputs given simply by running the MRE script twice:

# run 1
[
    0.3417887779985449, 0.30920347236629403, 1.08032672669357, 0.2899030041327702,
    0.40918883280256435, 0.30787214351509695, 0.47436434561546964, 0.7,
    -0.0, 0.6110814906624237, 0.3664840845336063, 0.28112449799196776,
    0.4031579034487437, -0.0, -inf, 0.30787214351509773,
]

# run 2
[
    0.1927098090330974, 0.5860119137613014, 0.43236992205527325, 0.2910544674330575,
    0.4931961506954208, 0.5730796542444605, 0.2858417922374956, 0.3687691136193972,
    0.3937717018101743, 0.29128690457493805, 0.6999999999999996, 0.33401438880103895,
    0.28410881021931295, 0.48800248009301384, 0.6854772138467992, -inf,
]

Additional Info

I've checked the correctness of the scipy outputs vs. cvxpy and multiple solver backends. The results always agree with scipy, which points to a bug in the simplex method implementation of QuantEcon.

[alberthli]

Resolved by using

linprog_simplex(c, A_eq=A, b_eq=b)

instead of

linprog_simplex(c, np.array([[]]), np.array([]), A, b)

[oyamad]

@alberthli Thank you for the report. Good that you found how to resolve the issues.
Maybe we should give useful examples in the docstring of linprog_simplex (#716).