Here is the feedback for your assignment 3 submission. First are the automated tests that check the correctness
of your implementation, then my comments.
Group: y453yang
==== dsm ====
[ OK ] Detected: Python 3
m = 2, n = 5 feas: ratio 1 x (0.10 / 0.100)
m = 3, n = 7 infeas: ratio 1.1 x (0.11 / 0.100)
m = 4, n = 12 feas: ratio 1 x (0.10 / 0.100)
m = 5, n = 20 infeas: ratio 1 x (0.11 / 0.110)
m = 6, n = 20 feas: ratio 1 x (0.11 / 0.110)
m = 7, n = 24 feas: ratio 1 x (0.11 / 0.110)
m = 8, n = 25 infeas: ratio 1.09 x (0.12 / 0.110)
m = 9, n = 25 feas: ratio 1 x (0.11 / 0.110)
m = 10, n = 20 feas: ratio 1 x (0.11 / 0.110)
m = 11, n = 22 infeas: ratio 1.09 x (0.12 / 0.110)
m = 12, n = 26 feas: ratio 1.09 x (0.12 / 0.110)
m = 13, n = 26 feas: ratio 1.09 x (0.12 / 0.110)
m = 14, n = 30 infeas: ratio 1.18 x (0.13 / 0.110)
m = 15, n = 32 feas: ratio 1.09 x (0.12 / 0.110)
m = 16, n = 40 feas: ratio 1.09 x (0.12 / 0.110)
m = 17, n = 42 feas: ratio 1.16 x (0.14 / 0.120)
m = 18, n = 44 infeas: ratio 1.08 x (0.13 / 0.120)
m = 19, n = 50 feas: ratio 1.16 x (0.14 / 0.120)
m = 20, n = 52 feas: ratio 1.16 x (0.14 / 0.120)
m = 30, n = 71 infeas: ratio 1.42 x (0.20 / 0.140)
m = 50, n = 98 feas: ratio 1.89 x (0.36 / 0.190)
m = 70, n = 145 feas: ratio 2.14 x (0.60 / 0.280)
m = 90, n = 190 infeas: timeout > 63.82 x (30.00 / 0.470)
m = 100, n = 280 feas: ratio 2.3 x (2.05 / 0.890)
m = 180, n = 600 infeas: timeout > 5.52 x (30.00 / 5.430)
[ OK ] Correctness tests passed: 23
==== comments ====
The code is very good, well written, and works fast. Unfortunately,
no measure is taken to deal with floating-point inaccuracies.
Specifically, on line 148, the test
if xB_tmp[i, 0] < l[set_B[i]] or xB_tmp[i, 0] > u[set_B[i]]:
should be
if xB_tmp[i, 0] < l[set_B[i]] - eps or xB_tmp[i, 0] > u[set_B[i]] + eps:
where eps = 1e-6. Note that on line 150, the test
j_type = 1 if xB_tmp[i, 0] < l[set_B[i]] else 2 should be changed accordingly into j_type = 1 if xB_tmp[i, 0] < l[set_B[i]] - eps else 2 And in the ratio test on lines 187-200, the comparisons with zero if a_i[0, k] < 0: and if a_i[0, k] > 0:
should become
if a_i[0, k] < 0 - eps: 1 and if a_i[0, k] > 0 + eps:
respectively.
Because of these floating-point inaccuracies, the code becomes slower on
larger infeasible instances, because some a_i[0, k] that should be zero
have small nonzero values (e.g. 1.2e-17), and become candidates for
further pivoting. If you add the tolerances “eps”, the code terminates
much earlier.
Specification: 1 / 1
Code: 2 / 2
Correctness: 4 / 4
Robustness: 0 / 4
Efficiency: 4 / 4
Total: 11 / 15
2