scipy: BUG: linprog, with highs is killed by the OOM killer when called with dense and large matrices

Describe your issue.

Hi, I have a bug when using the highs linprog solver with the code below.

The script is killed by the OOM killer. The problem arises when calling csc_matrix, which itself builds a coo_matrix, which calls the nonzeros method which is supposed to return the indices of non zero (far too many in this dense case).

Is it necessary to call csc_matrix here? It seems very inefficient for dense matrices. If such a transformation is necessary, it would be better that the code returns a python error to handle the problem correctly.

Reproducing Code Example

from scipy.optimize import linprog
import numpy as np
np.random.seed(0)
n_ctr = 500000
n_var = 500
c_ = np.ones(n_var)
A_ub = np.random.random((n_ctr, n_var))
b_ub = np.zeros((n_ctr, ))

res = linprog(c_, A_ub=A_ub, b_ub=b_ub, method='highs-ds', bounds=(0, None), options={'disp': True})

print('End')

Error message

150075 killed     python highs.py

SciPy/NumPy/Python version information

scipy==1.7.3, numpy==1.22.2, python==3.8.10

About this issue

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

Commits related to this issue

Most upvoted comments

By checking size of matrices and available memory? I’m not sure that’s necessary or desirable, it seems standard to let the user try even to the point of crashing.

Crashing is always a bug. I see slightly more verbose output with the reproducer in the issue description, but that should be considered a bug:

Running HiGHS 1.2.0 [date: 2021-07-09, git hash: n/a]
Copyright (c) 2022 ERGO-Code under MIT licence terms
Presolving model
terminate called after throwing an instance of 'std::length_error'
  what():  vector::_M_default_append
Aborted (core dumped)

What would we consider the “correct” behavior for the HiGHS wrapper?

It can’t be fixed in the wrapper if it’s crashing in HiGHS itself. Looking at how memory allocations in HiGHS, there is a random mix of usages of malloc, new and make_unique, and the malloc instances seem unprotected by checks for a null return value.

It seems to be like the HiGHS code should be audited for all memory allocations and improved, and once that is done it’s probably a matter of catching std::bad_alloc in the Cython wrapper and converting that into a Python exception.

I’d prefer to just close this unless we have a specific reason to assume that the reproducer in this issue is more likely to re-occur than other memory management issues in HiGHS. Tests like these are often expensive to run, prone to failure on low-memory systems, and don’t add much value.

can this be closed again @HaoZeke ?

As far as upstream is concerned (which we now track with #21565), yes (https://github.com/ERGO-Code/HiGHS/pull/1467#issuecomment-2352340825). I think it should stay open until a testcase is added for this within SciPy though.