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
- BUG: Fix gh-15888 More of a dodge than a fix, but will essentially work with exceptions now. — committed to HaoZeke/scipy by HaoZeke 3 years ago
- BUG: Fix gh-15888 More of a dodge than a fix, but will essentially work with exceptions now. — committed to HaoZeke/scipy by HaoZeke 3 years ago
- BUG: Fix gh-15888 More of a dodge than a fix, but will essentially work with exceptions now. — committed to HaoZeke/scipy by HaoZeke 3 years ago
- MAINT: Pin highs to a version without gh-15888 — committed to HaoZeke/scipy by HaoZeke 3 years ago
- MAINT: Pin highs to a version without gh-15888 — committed to HaoZeke/scipy by HaoZeke 3 years ago
- MAINT: Pin highs to a version without gh-15888 — committed to HaoZeke/scipy by HaoZeke 3 years ago
- MAINT: Pin highs to a version without gh-15888 — committed to HaoZeke/scipy by HaoZeke 3 years ago
- MAINT: Pin highs to a version without gh-15888 — committed to HaoZeke/scipy by HaoZeke 3 years ago
- MAINT: Pin highs to a version without gh-15888 MAINT: Switch to the scipy fork of highs TST: xfail known flaky test Co-authored-by: mckib2 <mckib2@users.noreply.github.com> MAINT: Add a note on .g... — committed to HaoZeke/scipy by HaoZeke 3 years ago
- MAINT: Pin highs to a version without gh-15888 MAINT: Switch to the scipy fork of highs TST: xfail known flaky test Co-authored-by: mckib2 <mckib2@users.noreply.github.com> MAINT: Add a note on .g... — committed to HaoZeke/scipy by HaoZeke 3 years ago
- MAINT: Pin highs to a version without gh-15888 MAINT: Switch to the scipy fork of highs TST: xfail known flaky test Co-authored-by: mckib2 <mckib2@users.noreply.github.com> MAINT: Add a note on .g... — committed to HaoZeke/scipy by HaoZeke 3 years ago
- MAINT: Pin highs to a version without gh-15888 MAINT: Switch to the scipy fork of highs TST: xfail known flaky test Co-authored-by: mckib2 <mckib2@users.noreply.github.com> MAINT: Add a note on .g... — committed to HaoZeke/scipy by HaoZeke 3 years ago
- MAINT: Pin highs to a version without gh-15888 MAINT: Switch to the scipy fork of highs TST: xfail known flaky test Co-authored-by: mckib2 <mckib2@users.noreply.github.com> MAINT: Add a note on .g... — committed to HaoZeke/scipy by HaoZeke 3 years ago
- MAINT: Pin highs to a version without gh-15888 MAINT: Switch to the scipy fork of highs TST: xfail known flaky test Co-authored-by: mckib2 <mckib2@users.noreply.github.com> MAINT: Add a note on .g... — committed to HaoZeke/scipy by HaoZeke 3 years ago
- MAINT: Pin highs to a version without gh-15888 MAINT: Switch to the scipy fork of highs TST: xfail known flaky test Co-authored-by: mckib2 <mckib2@users.noreply.github.com> MAINT: Add a note on .g... — committed to HaoZeke/scipy by HaoZeke 3 years ago
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:
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,newandmake_unique, and themallocinstances 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_allocin 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.
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.