[SCIP] how to augment the lower bound

[Brannon King]

> The only places where the dual bound plays a role other than pruning nodes are
> 1. in the updates of the pseudo costs, and
> 2. in the node selection.

Thank you for clarifying that usage. That was helpful.

> ... in discrete steps). This could lead to a situation in which the branching scores of
> all variables are identical or very similar and thus confuse the branching more than it helps.

Yes, I'm familiar with this problem. You have the same issue if you
try to solve the problem via A* search; the early nodes all have the
same overly-optimistic score. Actually, I think the solver struggles
with this some too on the early nodes.

> ... Thus, if you have good heuristics to produce
> good solutions quickly, or if SCIP finds good solutions anyway in the beginning of the
> search, then trying to improve the node selection is usually not too beneficial.

This has not been my experience at all. I have good heuristics. I can
give the solver the optimal solution right at the start, and it will
still take a long time to bring the lower bound up to that value.
That's the whole reason I was looking into overriding the lower bound.

> So, I would suggest that in a first step you only implement a cut separator that prunes a
> node if you can show that the node cannot improve the incumbent. This could be helpful.

If I return a lower bound that exceeds the best upper bound, I presume
this pruning should happen automatically?

>> It sounds like what you would like to do is write a custom relaxator
>> plugin in SCIP. If you give it a negative priority, it will be called
>> after the LP has been solved.

Thanks. I was able to make the custom relaxator execute. I did have to
make an adjustment to PySCIPOpt:
https://github.com/scipopt/PySCIPOpt/issues/735