Flow cover cuts

[Opt-Mucca]

This PR adds flow cover cuts to HiGHS. All logic related to the cut can be followed from the HighsCutGeneration::tryGenerateFLowCoverCut function. Currently the cuts are only generated based on rows in the LP, i.e., "aggregations" of size 1. The performance results are extremely finicky, but seem to be promising, and are especially so for some network based energy problems I've been testing on. This shouldn't be merged before any additional computational experiments are done. @galabovaa I changed the two tests because (1) the instance now solved at the root node and therefore has the optimal solution but has status interrupted (2) the primal heuristics now jumped quicker to the optimal solution, so I had to up the objective limit to still catch the event.

[codecov[bot]]

Codecov Report

:x: Patch coverage is 93.80665% with 41 lines in your changes missing coverage. Please review. :white_check_mark: Project coverage is 81.35%. Comparing base (e4632db) to head (7e3fbc5). :warning: Report is 25 commits behind head on latest.

Files with missing lines	Patch %	Lines
highs/mip/HighsTransformedLp.cpp	88.02%	37 Missing :warning:
highs/mip/HighsCutGeneration.cpp	99.12%	3 Missing :warning:
highs/lp_data/HighsOptions.h	75.00%	1 Missing :warning:

Additional details and impacted files

@@            Coverage Diff             @@
##           latest    #2518      +/-   ##
==========================================
+ Coverage   81.20%   81.35%   +0.14%     
==========================================
  Files         349      349              
  Lines       85465    86440     +975     
==========================================
+ Hits        69406    70327     +921     
- Misses      16059    16113      +54     

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.

:rocket: New features to boost your workflow:

• :snowflake: Test Analytics: Detect flaky tests, report on failures, and find test suite problems.

[Opt-Mucca]

One general question (- I have not thought this through -): Should new cut separators like flow cover cuts live in the HighsCutGeneration class or have its own (derived) class?

@fwesselm For the current design they shouldn't. Anything that is going to call CutGeneration::generateCut() should have its own file, e.g., if we create a new separator that identifies some network structure and aggregates certain LP rows we'd create something like HighsNetworkSeparator.cpp. The exception to this rule is something that is simply looping over some global data structure, e.g. separateImpliedBounds and separateCliques. Currently all the cut generators, e.g., separateLiftedKnapsackCover, cmirCutGenerationHeuristic, and now separateLiftedFlowCover, use the same data structures in HighsCutGeneration so are just functions in the single file. We could make some derived classes...... (After writing out my argument against I don't think the logic holds, so I'm on the fence). I'd still not push for putting them all into separate files, but it definitely makes more sense each time we add a new cut.

[Opt-Mucca]

@jajhall Currently the big hurdle is getting this to be performance improving on @fwesselm cluster. (Last time it was measured it was performance neutral). There's also the issue of some instances from those tests having slightly off results, but I either can't recreate them (something to do with the testing environment) or they've disappeared with more recent changes, and in some cases it's a deviation from a previously incorrect solution path..... Still looking into all of them. For the naming convention: I've been trying to mostly use underscores when I write new code, but the entire cut generation code uses camel case, and I'd rather fix that all at once instead of mix up the standard.

[jajhall]

Hmm... Can you easily switch off the flow cover constraints by default? That way the code is merged, possibly avoiding conflicts that might occur if merged later.

Probably a useless comment, but I have a memory of Philip Christophel saying that flow cover constraints weren't so useful until he revisited them...

[Opt-Mucca]

I can add a parameter to turn them off before they get merged. In the long term I'd like to add some high level cut parameters anyways (something like an emphasis setting) because it's clear some users want to test settings for their application. Currently I'm just trying to make it so the behaviour of when they're turned off is identical to before. For the second point: I think you're misremembering that with path mixing inequalities (he always presents them together). They're the cuts he thought weren't that helpful, and it took more instances being available and Leona trying them out to actually see that the cuts were good.