Segfault in presolve

[jajhall]

With issue-2095.mps, HiGHS segfaults in presolve.

See scipy/scipy#22188

[jajhall]

Bug not exhibited by issue-2095.lp.txt but this file is useful for studying the model.

Failure is in first reduction, when HPresolve::equalityRowAddition subtracts row 1
$x_2+x_{12} + x_{13} + x_{17} =1$
from row 2
$x_3+x_{12} + x_{13} + x_{17} =1$
since they are "parallel but for singletons", as $x_2$ and $x_3$ are both singletons. Naturally this will modify row 1 to
$-x_2+x_3=0$
allowing one of the variables to be removed.

[jajhall]

Despite being passed as const, the vector parameter of HPresolve::equalityRowAddition is being corrupted

The initial values

HPresolve::equalityRowAddition: -2 (const auto& lc_rowNz : vector) yields 2 11 12 16

are unchanged by calling postsolve_stack.equalityRowAddition

HPresolve::equalityRowAddition: -1 (const auto& lc_rowNz : vector) yields 2 11 12 16

In the loop for (const auto& rowNz : vector):

Pass 0 adds an entry to the matrix due to the nonzero in row 1 created by subtracting column 2 from row 1

HPresolve::equalityRowAddition: 0 (const auto& lc_rowNz : vector) yields 2 11 12 16 with rowNz.index() = 2
New nonzero 2

but the indices in vector are corrupted.

Pass 1 uses rowNz.index() = 12, (rather than 11) but (by chance) 12 is common, so pos = 15 is unlinked because it's removed from row 1.

HPresolve::equalityRowAddition: 1 (const auto& lc_rowNz : vector) yields -1 12 15 32 with rowNz.index() = 12 has pos = 15
Common nonzero 12

Pass 2 uses rowNz.index() = -1, and all hell breaks loose

HPresolve::equalityRowAddition: 2 (const auto& lc_rowNz : vector) yields -1 12 -1 32 with rowNz.index() = -1

[jajhall]

It would be good to know why adding the singletons to the matrix in the loop leads to corruption of the vector parameter of HPresolve::equalityRowAddition - and whether it can be avoided - however, performing the additions after the loop through vector avoids the consequences of corruption, and has no meaningful overhead.

Hence the issue, as posed, is closed by #2096

Also, are there any other uses of HPresolve::addToMatrix that may lead to similar corruption?

[fwesselm]

I think the issue is that a HighsMatrixSlice stores pointers to the respective vectors of indices, coefficients and positions. Now, this is fine in general, but if the index or coefficient vectors (Acol and/or Avalue) need to be re-sized and moved around in memory (for example, when a push_back is performed by HPresolve::addToMatrix), these pointers will be invalid. Thus, the code crashes. I will try to think about a good way to fix this.