scipy: Error in linprog with simplex method

My issue is about Error in scipy.optimize.linprog with simplex method. Mostly it works well. But I’ve found more than 15 cases that are soluble in matlab and can’t be solved by linprog with the default “method=simplex”. I first found this problem in scipy 0.19 and now it is updated to 1.2.1 but the problem remains the same. This problem can also be solved by passing “method=interior-point”. But usually simplex method is more popular. Hope fix it.

Reproducing code example:

from scipy.optimize import linprog

effective_A_ub = [[1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0],
                  [-1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0],
                  [7.800000190734863, 15.699999809265137, 15.09999942779541, 44.20000076293945, 0, 0, 0, 0, 0, 0, 0, 0],
                  [-7.800000190734863, -15.699999809265137, -15.09999942779541, -44.20000076293945, 0, 0, 0, 0, 0, 0, 0, 0],
                  [-1.6000001430511475, -6.5, -7.499999523162842, -5.900000095367432, 0, 0, 0, 0, 0, 0, 0, 0],
                  [0.019999999552965164, 0.10999999940395355, 0.15000000596046448, 0.33000001311302185, 23.290000915527344, 35.84000015258789, 0.30000001192092896, 0, 0, 0, 0, 0],
                  [-0.019999999552965164, -0.10999999940395355, -0.15000000596046448, -0.33000001311302185, -23.290000915527344, -35.84000015258789, -0.30000001192092896, 0, 0, 0, 0, 0],
                  [0.05000000447034836, 0.3199999928474426, 0.25, 0.1599999964237213, 17.0, 0, 0, 0, 0, 0, 0, 0],
                  [-0.05000000447034836, -0.3199999928474426, -0.25, -0.1599999964237213, -17.0, 0, 0, 0, 0, 0, 0, 0],
                  [0.05000000447034836, 0.14000000059604645, 0.1899999976158142, 0.07999999821186066, 0, 0.07999999821186066, 98.5, 0, 0, 0, 0, 0],
                  [-0.05000000447034836, -0.14000000059604645, -0.1899999976158142, -0.07999999821186066, 0, -0.07999999821186066, -98.5, 0, 0, 0, 0, 0],
                  [3390.0, 2240.0, 2760.0, 3370.0, 0, 0, 0, 0, 0, 0, 8750.0, 0],
                  [-3390.0, -2240.0, -2760.0, -3370.0, 0, 0, 0, 0, 0, 0, -8750.0, 0],
                  [0.17020000517368317, 0.45989999175071716, 0, 2.3584001064300537, 0, 0, 0, 0, 0, 0, 0, 78.80000305175781],
                  [-0.17020000517368317, -0.45989999175071716, 0, -2.3584001064300537, 0, 0, 0, 0, 0, 0, 0, -78.80000305175781],
                  [-0.055499997735023496, 0.023399996757507313, 0.00040000975131987415, 0.27890002727508545, 0.0, 0.0, 0.0, -98.0, 0.0, 0.0, 0.0, 23.64000091552734],
                  [-0.10650000870227813, -0.03399997353553774, -0.0011999845504760964, 0.5369000434875488, 0.0, 0.0, 0.0, -98.0, 0.0, 0.0, 0.0, 47.28000183105468],
                  [-0.07380000725388527, 0.08950000405311587, 0.4680000185966492, 0.3227000832557678, 0.0, 0.0, 0.0, 0.0, -98.0, 0.0, 0.0, 51.22000198364258]]
effective_b_ub = [1.0, -1.0, 19.0, -18.0, -3.5, 0.9, -0.7, 0.5, -0.4, 0.6, -0.4, 2950.0, -2900.0, 0.7, -0.6, 0, 0, 0]
c = [2100.0, 1800.0, 1750.0, 2750.0, 1900.0, 300.0, 700.0, 20000.0, 7000.0, 25000.0, 6000.0, 8000.0]
adjusted_bounds = [(0, 1), (0, 0.3), (0, 0.2), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0.01, 0.01), (0, 0.02), (0, 1)]
A_eq = [[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]]
b_eq = [1]
res = linprog(c=c, A_ub=effective_A_ub, b_ub=effective_b_ub, A_eq=A_eq, b_eq=b_eq, bounds=adjusted_bounds)
print(res)

Error message:

Traceback (most recent call last):
  File "<stdin>", line 35, in <module>
      res = linprog(c=c, A_ub=effective_A_ub, b_ub=effective_b_ub, A_eq=A_eq, b_eq=b_eq, bounds=adjusted_bounds)
  File "D:\ProgramData\Anaconda3\lib\site-packages\scipy\optimize\_linprog.py", line 478, in linprog
    complete, undo, status, message, tol, iteration, disp)
  File "D:\ProgramData\Anaconda3\lib\site-packages\scipy\optimize\_linprog_util.py", line 1322, in _postprocess
    lb, ub, tol, message
  File "D:\ProgramData\Anaconda3\lib\site-packages\scipy\optimize\_linprog_util.py", line 1235, in _check_result
    raise ValueError(message)
ValueError: Phase 1 of the simplex method failed to find a feasible solution. The pseudo-objective function evaluates to 3.6e-11 which exceeds the required tolerance of 1e-12 for a solution to be considered 'close enough' to zero to be a basic solution. Consider increasing the tolerance to be greater than 3.6e-11. If this tolerance is unacceptably  large the problem may be infeasible.

Process finished with exit code 1

Scipy/Numpy/Python version information:

About this issue

Original URL
State: closed
Created 5 years ago
Comments: 17 (8 by maintainers)

Most upvoted comments

@BinglePan thanks for taking the time to submit an issue and offering to help.

I first found this problem in scipy 0.19 and now it is updated to 1.2.1 but the problem remains the same. This problem can also be solved by passing “method=interior-point”. But usually simplex method is more popular.

As @mdhaber said, from 1.3 onwards the interior-point and revised simplex are the default solvers with the original simplex being maintained for legacy or educational use.

I’ve investigated the reference for linprog finding that the default value for tolerance is options={‘tol’: 1e-12}. This time my case can be solved by loosening the tolerance. Maybe so can the other 14 cases I encountered.

We’ve raised the tolerance to 1e-9 in 1.4 (see: #10143) making many of the existing tolerance issues pass (but still fail with 1e-12) without any failures on our existing tests. Maybe try it with the

But now my question is when I should use the default value for tol and if not what value for it should be set.

The error message prints the value of the phase one objective function (in your example 3.6e-11). That would be a good start. The issue with a default tolerance is that for any tolerance a problem could be constructed to make it fail.

@mdhaber I won’t have time to take an in-depth look at it, the error looks related to the tolerance value (as changing from 1e-12 to 1e-11 fixes the issue) which will be updated in 1.4 and occurs for the simplex method only, which is no longer the default, nor recommended.

Kai-Striega on Aug 16, 2019