scipy: BUG: scipy.optimize.linprog gives optimized solution which does not respect linear equation
Describe your issue.
in the code example below the solution fond by linprog does not respect the linear equation even though it claims otherwise. If I run the code snippet below, I get the following output
norm residual x on input equation is 0.021185053416350418 norm residual x given by linprog is 0.0
Reproducing Code Example
import numpy as np # version 1.26.4
import scipy # version 1.12.0
if __name__ == '__main__':
boundaries=[(10000.0, 9010000.0), (0.0, None), (10000.0, None), (0.0, 84.62623413258109), (10000.0, None), (10000.0, None), (10000.0, None), (10000.0, None), (10000.0, None), (10000.0, None), (10000.0, None), (10000.0, None), (10000.0, None), (None, None), (None, None), (None, None), (None, None), (None, None), (None, None), (None, None), (None, None), (None, None), (None, None), (None, None), (None, None), (None, None), (None, None), (None, None), (None, None), (None, None), (None, None), (None, None), (None, None)]
eq_entries=[-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, 0.001, -0.001, 3.7337777768059636e-10, 3.7337777768059636e-10, 1.0, -1.0, 0.001, -0.001, 3.7337777768059636e-10, 3.7337777768059636e-10, 1.0, -1.0, 0.001, -0.001, 3.7337777768059636e-10, 3.7337777768059636e-10, 1.0, -1.0, 0.001, -0.001, 3.7337777768059636e-10, 3.7337777768059636e-10, 1.0, -1.0, 0.001, -0.001, 3.7337777768059636e-10, 3.7337777768059636e-10, 1.0, -1.0, 0.001, -0.001, 3.7337777768059636e-10, 3.7337777768059636e-10, 1.0, -1.0, 0.001, -0.001, 3.7337777768059636e-10, 3.7337777768059636e-10, 1.0, -1.0, 0.001, -0.001, 3.7337777768059636e-10, 3.7337777768059636e-10, 1.0, -1.0, 0.001, -0.001, 3.7337777768059636e-10, 3.7337777768059636e-10, 1.0, -1.0, 0.001, -0.001, 3.7337777768059636e-10, 3.7337777768059636e-10, 1.0, -1.0]
eq_indizes=[0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 11, 11, 12, 12, 12, 12, 13, 13, 14, 14, 14, 14, 15, 15, 16, 16, 16, 16, 17, 17, 18, 18, 18, 18, 19, 19, 20, 20, 20, 20, 21, 21, 22, 22, 22, 22, 23, 23, 24, 24, 24, 24, 25, 25, 26, 26, 26, 26, 27, 27, 28, 28, 28, 28, 29, 29, 30, 30, 30, 30, 31, 31]
eq_vars=[15, 14, 17, 16, 19, 18, 21, 20, 23, 22, 25, 24, 27, 26, 29, 28, 31, 30, 13, 1, 0, 32, 3, 14, 13, 4, 0, 4, 0, 32, 31, 2, 12, 2, 12, 16, 15, 5, 4, 5, 4, 18, 17, 6, 5, 6, 5, 20, 19, 7, 6, 7, 6, 22, 21, 8, 7, 8, 7, 24, 23, 9, 8, 9, 8, 26, 25, 10, 9, 10, 9, 28, 27, 11, 10, 11, 10, 30, 29, 12, 11, 12, 11]
eq_values=[0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 9000000.0, 0.0, 0.006587392118285457, -5032.197406716549, 0.0041860502789104696, -7918.93439542944, 0.0063205763583549035, -5244.625751707402, 0.006053760598424349, -5475.7793929428, 0.005786944838493795, -5728.248403917573, 0.0055201290785632405, -6005.123623538355, 0.005253313318632687, -6310.123825488683, 0.004986497558702133, -6647.763714796453, 0.004719681798771578, -7023.578908071522, 0.004452866038841024, -7444.431798646482]
coefficients=[0.0, 0.0, 0.0, -0.011816666666666668, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]
np_eq_entries=np.asarray(eq_entries,dtype=np.float64)
np_eq_indizes=np.asarray(eq_indizes,dtype=np.int32)
np_eq_vars=np.asarray(eq_vars,dtype=np.int32)
a_eq=scipy.sparse.csr_array((np_eq_entries,(np_eq_indizes, np_eq_vars)),shape=(32,33))
b_eq=np.asarray(eq_values,dtype=np.float64)
c=np.asarray(coefficients,dtype=np.float64)
assert len(b_eq)==32
assert len(c)==33
assert len(boundaries)==33
result = scipy.optimize.linprog(c, A_ub=None, b_ub=None, A_eq=a_eq, b_eq=b_eq, bounds=boundaries)
assert result.status==0
x=result.x
b_x=a_eq @ x
r_x=b_x-b_eq
n_r_x=np.linalg.norm(r_x)
r=result.eqlin.residual
n_r=np.linalg.norm(r)
print("norm residual x on input equation is %s"%n_r_x)
print("norm residual x given by linprog is %s"%n_r)
Error message
None
SciPy/NumPy/Python version and system information
1.12.0 1.26.4 sys.version_info(major=3, minor=9, micro=13, releaselevel='final', serial=0)
Build Dependencies:
blas:
detection method: pkgconfig
found: true
include directory: /c/opt/64/include
lib directory: /c/opt/64/lib
name: openblas
openblas configuration: USE_64BITINT= DYNAMIC_ARCH=1 DYNAMIC_OLDER= NO_CBLAS=
NO_LAPACK= NO_LAPACKE= NO_AFFINITY=1 USE_OPENMP= SKYLAKEX MAX_THREADS=2
pc file directory: c:/opt/64/lib/pkgconfig
version: 0.3.21.dev
lapack:
detection method: pkgconfig
found: true
include directory: /c/opt/64/include
lib directory: /c/opt/64/lib
name: openblas
openblas configuration: USE_64BITINT= DYNAMIC_ARCH=1 DYNAMIC_OLDER= NO_CBLAS=
NO_LAPACK= NO_LAPACKE= NO_AFFINITY=1 USE_OPENMP= SKYLAKEX MAX_THREADS=2
pc file directory: c:/opt/64/lib/pkgconfig
version: 0.3.21.dev
pybind11:
detection method: config-tool
include directory: unknown
name: pybind11
version: 2.11.1
Compilers:
c:
commands: cc
linker: ld.bfd
name: gcc
version: 10.3.0
c++:
commands: c++
linker: ld.bfd
name: gcc
version: 10.3.0
cython:
commands: cython
linker: cython
name: cython
version: 3.0.8
fortran:
commands: gfortran
linker: ld.bfd
name: gcc
version: 10.3.0
pythran:
include directory: C:\Users\runneradmin\AppData\Local\Temp\pip-build-env-rikezz0v\overlay\Lib\site-packages/pythran
version: 0.15.0
Machine Information:
build:
cpu: x86_64
endian: little
family: x86_64
system: windows
cross-compiled: false
host:
cpu: x86_64
endian: little
family: x86_64
system: windows
Python Information:
path: C:\Users\runneradmin\AppData\Local\Temp\cibw-run-ee1litsm\cp39-win_amd64\build\venv\Scripts\python.exe
version: '3.9'
About this issue
- Original URL
- State: open
- Created 3 years ago
- Comments: 15 (8 by maintainers)
I should add that, rather than decrease the value of ‘small_matrix_value’ used by SciPy, the warning returned from passModel when small values are ignored should be communicated to the SciPy user
Thanks @lucascolley, I’ll try tomorrow. Too late now 😅
Thanks @jajhall - if you could try it with C++, let us know what happens. Thanks for the offer @lucascolley - let’s take you up on that if it’s not reproducible in C++.
If you are unable to reproduce the behaviour in C++, I can try to create a highspy reproducer.
It does check the value, but…
… only to check if there is an error. If there’s a warning, it doesn’t do anything.
If I add a line to print out the value of
init_status, I get the following for the reprex in this case:So HiGHS is returning that there is a warning.
Armed with this, I could write a piece of code which checks if there’s a warning, then tells the user to turn on detailed logging.
Ideally, though, we would cut out the middle-man, and just tell the user what the warning was. I was looking through the source code of highsLogUser(), and I realized that it accepts a callback to customize how logs are handled. We could set up a callback that records every warning that was seen while passing, presolving, or running the model.
You can use this from Python, too. You just need to set up a callback like this:
I wrote a branch that uses this approach to turn HiGHS warnings into Python warnings. For the reprex in this issue, it prints the following:
The branch can be found here: https://github.com/scipy/scipy/compare/main...nickodell:scipy:njo-log-warnings?expand=1
What do you think of this approach? There might be a performance hit, since it calls this callback every time there is a log message of any severity, not just warnings.
The problem is that the very small values in the matrix are ignored by HiGHS.
I’ve reproduced this (in C++) and get the following
and then, after solving, I get
If I set the
small_matrix_valueoption to1e-12, as followsthen, after solving, I get
Conclusion: this is a very badly scaled model, and HiGHS has to protect itself against trying to solve models where such small matrix values are meaningful, as they can lead to numerical failure of the LP solvers. That said, in this case, the LP is so easy to solve - it’s reduced to empty in presolve - that the small values aren’t a problem.
@fancidev: You are trying to solve my optimization problem. The problem here is a bug with linprog. It may be ok if linprog doesn’t find a solution, it may be ok if it finds a bad (almost) solution with a residuum>0, but claiming to have found a solution with residuum 0 when in fact the solution given has a quite large residuum is simple a bug. I’m now using google ortools and can work with these, but I think people should also be able to work with scipy …