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)

Most upvoted comments

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.

The occurrence of a warning like this results in a status return from passModel of kWarning, so it is available in code, not just from logging.

Surely SciPy tests all status return values from highspy and takes appropriate action

It does check the value, but…

    init_status = highs.passModel(lp)
    if init_status == _h.HighsStatus.kError:
        # code to handle error here
    # continues normally

… 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:

HighsStatus.kWarning

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.

    init_status = highs.passModel(lp)
    if init_status == _h.HighsStatus.kError:
        # existing error handling code
    elif init_status == _h.HighsStatus.kWarning:
        warn(
            "A warning was encountered while passing the model. "
            "Set options={'disp': True'} to see it.",
            OptimizeWarning,
            stacklevel=3,
        )

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:

highs = _h._Highs()
highs.setCallback(some_callable, None)
highs.startCallback(_h.cb.HighsCallbackType.kCallbackLogging)

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:

/home/nodell/scipy/../foo/bug-20336.py:22: OptimizeWarning: LP matrix packed vector contains 20 |values| in [3.73378e-10, 3.73378e-10] less than or equal to 1e-09: ignored

  result = scipy.optimize.linprog(c, A_ub=None, b_ub=None, A_eq=a_eq, b_eq=b_eq, bounds=boundaries, options=dict(disp=False))

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

WARNING: LP matrix packed vector contains 20 |values| in [3.73378e-10, 3.73378e-10] less than or equal to 1e-09: ignored

and then, after solving, I get

norm residual x on input equation is 0.0211851 norm residual x given by linprog is 0

If I set the small_matrix_value option to 1e-12, as follows

highs.setOptionValue(“small_matrix_value”, 1e-12);

then, after solving, I get

norm residual x on input equation is 1.27628e-09 norm residual x given by linprog is 0

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 …