Set cover like instance with strange presolver behavior & LpIters bug

[Athlici]

While solving some set cover like instances with HiGHS we have encountered some undesirable behaviors in regards to presolving, all reproducible with the instance dump.zip.

• For reference, with presolve disabled the instance is solved in ~6min HiGHSPoff.log.
• Presolve however takes very long (~4,5 hours), uses a lot of memory (~22GB) and the resulting instance then takes longer to solve than without presolve HiGHSPon.log.
• With presolve enabled but presolve_reduction_limit=0 the instance is solved quickly (30s) but the LpIter counter takes on huge values (~10^9) HiGHSRed0.log.

Our problem structure is relative simple and is essentially given by $$\min \sum_{i=1}^n c_i*x_i\quad\text{s.t.}$$ $$\sum_{i=1}^n \gamma_{i,j}*x_i = d_j\quad\text{for}\quad j=1,\ldots,m$$ $$\sum_{i=1}^n x_i\leq 10000$$ $$0\leq x_i\leq u_i\quad\text{for}\quad i=1,\ldots,n$$ with m small, n large and the upper bounds generally superfluous for the solution. The coefficients $\gamma_{i,j}$ represent configurations and are non-negative integers, $d_i$ are integer amounts and $c_i$ are positive costs. With higher variable counts the problems mentioned above become more pronounced.

Unfortunately presolve enabled with presolve_reduction_limit=0 leads to issues on other instances, see issue 1578. For the moment we are just disabling presolve completely to work around these issues. Ideally though presolve should probably not exhibit these detrimental effects, which is why we thought that you might be interested in this instance.

[jajhall]

The short answer is that 56% (605612/108000) of your coefficient matrix entries are nonzero, so presolve is unlikely to reduce the size of the problem to be solve. All that happens is that about 7000 nonzeros are removed. Hence you should run with presolve=off (rather than setting presolve_reduction_limit=0).

That said, HiGHS shouldn't run presolve for as long as you experienced, or use such a vast amount of memory for a modest-sized problem. In my case, the run was just killed.

I'll try to get to the bottom of the issue later

[jajhall]

The culprit (@fwesselm) is probing. I've added another bit to the presolve_rule_off option so that probing can be prevented. This leads to presolve taking 30s, and the MIP is solved in 147s. I don't know why probing can have such a large memory requirement.

[jens-diewald]

Hi @jajhall, thanks for looking into this.

Hence you should run with presolve=off (rather than setting presolve_reduction_limit=0).

My observation was, that presolve_reduction_limit=0 ist stronger than presolve=off, as it also deactivates later presolve steps during Branch & Cut. Is that correct? Would you still generally recommend against using presolve reduction limit=0? Note the timings mentioned by @Athlici above: presolve=off: ~6min, presolve_reduction_limit=0: ~30s

[jajhall]

Very interesting, I'd not considered that consequence. Indeed, for your purposes reduction_limit=0 is the way to go

[jens-diewald]

Alright, thanks for the clarification! I do not know how relevant this example seems to you. It is an artificial test case on our side. But it may also be worth noting, that CBC (single threaded) solves it (and similarly constructed problems) in <10s with presolve enabled, so maybe there is something to be learned there? SCIP does also spend a huge amount of time on presolving and especially probing. Gurobi takes <2s.

[jajhall]

Clearly HiGHS gets too excited about probing, and it will be good to find out why. In particular to find out why the memory use snowballs. CBC may gain by being less sophisticated as a MIP solver.

[jajhall]

Can you generate an example that is (say) ten times smaller? This is likely to make it much easier to study. Thanks

[jens-diewald]

Sure, here you go: smaller_examples.zip I have included three different sizes, the file names correspond to the problem sizes. I did not have much time to look at them in detail, but i think all of them exhibit the problem (on a smaller scale). CBC still solves all three of these well within one second.

[jajhall]

Thanks, I can see that the overhead of probing is exhibited by the smallest of these.

However, I'm currently looking at the LP iteration count "explosion", and it only happens for 9x120000.mps, and not for 7x17492.mps or smaller instances.

Please could you let me have the 8xN.mps problem?

[jajhall]

Note that lp_iterations is a pseudo-measure of work, rather than actual number of simplex iterations performed, so the value quoted here isn't "real"

I guess that this measure of work aids the decision on whether sub-MIPs are solved when applying primal heuristics. Perhaps the reason why it blows up is indicative of circumstances where sub-MIPs being solved is particularly inadvisable

@Opt-Mucca I've tracked down adjustmentfactor in HighsPrimalHeuristics::solveSubMip as the cause of lp_iterations blowing up as the sub-MIP level decreases.

[jens-diewald]

Please could you let me have the 8xN.mps problem?

I see that you figured something out without it. Do you still want some other problem sizes?

[jajhall]

We may be OK now, but the "8" problem might still be useful if it's easy to generate, thanks

[Opt-Mucca]

To give some info on why the instance takes so long to solve. HiGHS is iterating over each of the constraints and for each binary variable in the constraint finding a substantial amount of variable upper bounds for the integer variables, e.g., x_10 <= 10z_1 + 2 (where x is a general integer and z is a binary). The entire instance here consists of such constraints, so the worst-case complexity is being hit and it's essentially doing this for n_rows * n_bin_vars * n_int_vars (which also get called in the sub-mip). Normally this would hit some limit, but apparently limits are not so simple for vubs / vlbs as they're stored in the HighsHashTree class, and querying the hash tree to avoid collisions and cleaning everything up is then just dominating the solve time.

Need to think a bit on the best way to fix this (either try and limit the amount of variable bounds or identify this issue earlier). Just wanted to give some context as this issue is active. Will look into the lp iterations now.

To further clarify: It is not the actual standard probing causing this (even though this happens in the probing call). It is all the additional information being picked up when HiGHS is trying to identify cliques.

A double edit: There is also a major issue in time consumed on identifying common cliques when checking if one column dominates another.

[jens-diewald]

We may be OK now, but the "8" problem might still be useful if it's easy to generate, thanks

It's not much effort. (Note that it is not the "8" problem, I could also generate one with more/less columns.) 8x28907.zip

[Opt-Mucca]

@jajhall I would be in favour of removing the adjustment factor.

I guess the intended purpose is to inflate the numbers so that they better translate to work done on something like the original problem size (although that would then be 1 / adjustmentFactor)? Regardless, I find it very unintuitive to interpret for a standard user, and think any factor is prone to fail without enforcing some fixed recursion depth. It's also unintuitive because the budget for calling more heuristics is influenced heavily by this scaling.

[jajhall]

It's not much effort. (Note that it is not the "8" problem, I could also generate one with more/less columns.)

Thanks, let's see how @Opt-Mucca gets on

[jajhall]

@jajhall I would be in favour of removing the adjustment factor.

I guess the intended purpose is to inflate the numbers so that they better translate to work done on something like the original problem size (although that would then be 1 / adjustmentFactor)? Regardless, I find it very unintuitive to interpret for a standard user, and think any factor is prone to fail without enforcing some fixed recursion depth. It's also unintuitive because the budget for calling more heuristics is influenced heavily by this scaling.

@lgottwald will have implemented the adjustment with good reason, and it appears to have proved its value for the benchmark performance. I'm not aware of seeing such explosions before so, like the probing complexity, it may be just an artefact of these problems being strange. Perhaps you could talk to Leona about the adjustment factor.

[Opt-Mucca]

I've pushed some changes to branch fix-2326. It sadly doesn't make the instance solve in <2s, but it should halve the time of the smaller ones and make the largest one now solve in 10mins instead of 5 hours. I've just added an upper limit on how many vubs / vlbs can be stored and made a few if statements more efficient when they're being checked.

The core problem remains that HiGHS is essentially generating all this information it believes will be useful (and would be useful in most cases), but is completely unnecessary for this problem. A finely tuned if statement in the right place and some better heuristics would make this solve incredibly quicker, but I don't see such an if statement being triggered for 99.9999% of use cases.

[jajhall]

OK thanks, we'll see what the regression tests make of these changes

[Opt-Mucca]

@jajhall I've added a fix for the adjustment factor. The error was that its query to the submip for number of columns seemed to include the columns that were fixed in the original mip (via global domain changes unrelated to the heuristic fixings). So if the amount of global fixings was substantially larger than the fixings made for the submip, then the factor goes positive (which it shouldnt).

After talking to Leona about the factor: It seems that LP iterations as reported in the log are a proxy for "effort" or "work". One essentially wants to cheapen the LP iterations in the submip when recording because they're done on a smaller problem.

[jajhall]

@jajhall I've added a fix for the adjustment factor. The error was that its query to the submip for number of columns seemed to include the columns that were fixed in the original mip (via global domain changes unrelated to the heuristic fixings). So if the amount of global fixings was substantially larger than the fixings made for the submip, then the factor goes positive (which it shouldn't).

Great, thanks. Since the old adjustment factor was leading to excessive inflation of (proxy) LP iteration counts in sub-MIPs, it'll be interesting to see whether this correction leads to performance gains.

After talking to Leona about the factor: It seems that LP iterations as reported in the log are a proxy for "effort" or "work". One essentially wants to cheapen the LP iterations in the submip when recording because they're done on a smaller problem.

Thanks: it makes sense that this is what the proxy should have been doing