Linprog incorrect answer

[martin4396]

Problem Hi, I am using linprog_simplex() and get an incorrect result from this function. It is a corner case that only one feasible point in the feasible region. However, linprog_simplex() gives another point which doesn't satisfy the constraints and still says successfully solved the problem

Reproduce Error The input is

C = np.array([-392.62555556, 1260.73744444])
A_ub = np.array([[1, 0.1], [-1, -0.1], [1, 1]])
b_ub = np.array([10,-10,10])

The output from linprog_simplex(C,A_ub,b_ub) is

SimplexResult(x=array([ 0., 10.]), lambd=array([   0.        ,    0.        , 1260.73744444]), fun=12607.3744444, success=True, status=0, num_iter=5)

The output from scipy.optimize.linprog(-C,A_ub,b_ub)is (using -c here because scipy defaults to minimize but linprog_simplex defaults to maximize)

     con: array([], dtype=float64)
     fun: 3926.2555555895688
 message: 'Optimization terminated successfully.'
     nit: 6
   slack: array([ 1.30739863e-11, -1.30739863e-11,  9.40403311e-12])
  status: 0
 success: True
       x: array([1.00000000e+01, 4.07594499e-12])

We can see that the solution provided by linprog_simiplex doesn't meet the second constraint. The only one possible solution for this problem is x:array([10,0]) Version scipy: 1.7.3 linprog_simplex: latest

[martin4396]

One can say that the above formulation is bad because it is indeed 10<=x+0.1y<=10. I can give another example.

C = np.array([-4.09555556,  4.59044444])
A_ub = np.array([[1, 0.1], [-1, -0.1], [1, 1]])
b_ub = np.array([9.1,-0.1,0.1])

linprog_simplex gives:

SimplexResult(x=array([0. , 0.1]), lambd=array([0.        , 0.        , 4.59044444]), fun=0.459044444, success=True, status=0, num_iter=5)

Scipy gives:

     con: array([], dtype=float64)
     fun: 0.4095555559908888
 message: 'Optimization terminated successfully.'
     nit: 5
   slack: array([ 9.00000000e+00,  1.66781866e-12, -4.53735660e-12])
  status: 0
 success: True
       x: array([1.00000000e-01, 3.18837839e-12])

[oyamad]

@martin4396 Thank you for reporting. I will look into it.

[oyamad]

Now I see the problem: The current implementation of Phase 1 fails to handle the case where (0 is attained and) some of the artificial variables remain in the final basic solution. I think I know how to fix it and will do later...

[martin4396]

Thank you!