Out-of-bounds access in HighsSymmetryDetection::partitionRefinement

[falk-hueffner]

The following model crashes on Linux x86-64 and also MacOS arm64:

highs_crashmodel.mps.gz

It acrashes with default options but also deterministically (highs --parallel off --threads 1 highs_crashmodel.mps). I was unable to meaningfully reduce the size of the crashing instance, looks like a fairly specific path is needed.

ASAN nails it down to an out-of-bounds access: at HighsSymmetry.cpp around line 912 we have cellEnd < cellStart which makes std::partition fault.

It seems that the pruning around line 979:

      currentPartitionLinks[firstCellStart] = cellEnd;

      // undo possibly incomplete changes done to the cells
      for (--i; i >= refineStart; --i)
        updateCellMembership(i, firstCellStart, false);

causes this to become corrupt. I tried to remove that and rely on them be removed by backtracking of the caller together with all other cells created for this node, and that fixes the issue.

[jajhall]

Thanks for flagging this up, and proposing a fix. I'm sure that one of @Opt-Mucca and @fwesselm can take it from here.

[Opt-Mucca]

I've managed to recreate the issue on v1.15.1. I'll try and fix it by the end of the day. @falk-hueffner any chance you feel like giving a description on what the attached instance is?

[falk-hueffner]

The instance is from research related to combinatorial problems (which turned out to be a dead end). It's slightly minified so as is it doesn't make sense. In case you're interested, I'm attaching a (Claude generated) script that generates such instances.

highs_crashmodel_gen.py

[Opt-Mucca]

Update: I think I have a fix, but I'd like to test it overnight before being more confident in it. The symmetry code is my current blind spot w.r.t. MIP code coverage.

Thanks for pointing out that removing the pruning code worked @falk-hueffner It narrowed down the search by a fair bit. I believe the issue is that the pruning is not updating all data structures.