CODEWITHSUNDEEP
pythonscipylinear-programming
user1700890
user1700890

Reputation: 7730

linprog in scipy.optimize - checking solution

I tried to solve linear system with constraints using linprog from scipy.optimize, but got answer contradicting some inequalities. Here is my set up:

import numpy as np
from scipy.optimize import linprog
c = np.array([1,0,0,0,0,0,0])
A_ub = np.identity(7)*(-1)
b_ub = np.array([[-2],[-2],[-2],[-2],[-2],[-2],[-2]])
A_eq = np.array([[1,1,1,1,1,1,0],[0.3,1.3,0.9,0,0,0,-1],[0.3,0,0,0,0,0,-2/3],
                 [0,0.65,0,0,0,0,-1/15],[0,0,0.3,0,0,0,-1/15]])
b_eq = np.array([[100],[0],[0],[0],[0]])
res = linprog(c = c, A_ub=A_ub, b_ub=b_ub, A_eq = A_eq, b_eq = b_eq)

Here is the answer:

fun: -0.0
 message: 'Optimization terminated successfully.'
     nit: 15
   slack: array([ -2.,  -2.,  -2.,  94.,   0.,   0.,  -2.])
  status: 0
 success: True
       x: array([  0.00000000e+00,  -8.88178420e-16,  -1.77635684e-15,
         9.60000000e+01,   2.00000000e+00,   2.00000000e+00,
        -7.10542736e-15])

As you can see x_2 => 8.88178420e-16 is not smaller than -2.

Can somebody clarify why it happens?

Here is link to documentation: linprog

Upvotes: 1

Views: 1286

Answers (1)

sascha
sascha

Reputation: 33532

In general, scipy's linprog (method='simplex') is somewhat broken and not maintained much anymore.

Negative slacks like:

slack: array([ -2.,  -2.,  -2.,  94.,   0.,   0.,  -2.])

should never result in a valid solution!

While i saw some bad things in linprog (not finding an existing feasible solution), this looks very very bad (claiming an infeasible solution to be correct)!

So three things:

  • scipy >= 1.0 has a new Interior-point based LP-solver method='interior-point' which is more robust and more advanced
    • algorithmic-wise very different!
    • for use-cases like yours the only difference (apart from robustness and performance) is in the nature of solutions:
      • not guaranteed to be basic solutions (no support for cross-over; commercial solvers allow that)!
  • use the bounds argument instead of those inequalities to describe variable-bounds!
    • more specialized handling!
  • you described: -x <= -2 <-> x >= 2
    • the expected and correct solution is x >= 2!

IPM on your code:

     con: array([ 2.77992740e-10, -1.52664548e-11,  3.69659858e-12, -5.92570437e-12,
       -2.37077025e-12])
     fun: 43.3333333331385
 message: 'Optimization terminated successfully.'
     nit: 5
   slack: array([4.13333333e+01, 6.92779167e-13, 2.33333333e+00, 1.47777778e+01,
       1.47777778e+01, 1.47777778e+01, 1.75000000e+01])
  status: 0
 success: True
       x: array([43.33333333,  2.        ,  4.33333333, 16.77777778, 16.77777778,
       16.77777778, 19.5       ])

Upvotes: 1

Related Questions