[SCIP] how to augment the lower bound

[Tobias Achterberg]

Hi Brannon,

in my experience, increasing just the dual bound at the node (without moving the LP 
solution vector accordingly) is not terribly useful for improving performance. Basically, 
the only thing that matters w.r.t. bound value is whether you can cut off a node or not. 
So, if you can use your problem knowledge to prove that a certain node cannot improve the 
incumbent solution, then this will be strong. If you can only say that the bound is a bit 
better than what the LP says, then my guess is that this won't help too much, except if 
you then later find an incumbent that allows to cut off this node.

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.

For 1., the effect can be pretty significant. But a change that you are considering could 
actually be detrimental for the pseudo cost updates, in particular when your dual bound 
improvement leads often to the same values (e.g., because you can tighten the makespan 
always 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.

For 2., the node selection is mostly concerned with finding good feasible solutions 
earlier during the search. It is not that important for reducing the time to prove 
optimality (i.e., increase the dual bound). 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.


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. 
And then, you could try more, but my guess is that this will be much harder to achieve.


Regards,

Tobias


Am 2023-10-16 um 19:17 schrieb Gerald Gamrath:
> Hi Brannon,
> 
> your idea to extend the LP relaxator was going in the right direction. 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. See 
> https://www.scipopt.org/doc-8.0.3/html/RELAX.php for more details and perhaps also check 
> out the relaxator example.
> 
> Best,
> 
> Gerald
> 
> On 16.10.23 18:39, Brannon King wrote:
>> I have a scheduling problem with a poor LP relaxation. However, given
>> a relaxed solution, I can augment that using some additional problem
>> knowledge. In other words, I want the ability to manually increase
>> every node's lower bound.
>>
>> When I attempt to do this via cuts, either up front or lazily, my
>> problem takes longer to solve. This is a common problem in scheduling
>> problems; cuts that try to prop up the makespan destroy the search
>> direction. How can I use my augmented relaxation without destroying
>> the search direction? I picture that my improved lower bound would
>> eliminate poor subtrees sooner, but it would not change the overall
>> branching strategy.
>>
>> I originally pictured that I would take the LP relaxator, inherit from
>> it, and make a minor modification to where it sets the lower bound. In
>> looking around, though, it seems that the LP relaxation is not in a
>> plugin. Where is it done presently? Where would I intercept this?
>>
>> Maybe I should use a node selector plugin? This seems different than
>> overriding the lower bound, though. I don't understand how the node
>> priority is set already. Does it come from the lower bound? Or is it
>> based on properties of the variables, which one looks like it needs to
>> branch, etc?
>>
>> Thanks for your time,
>> Brannon
>> _______________________________________________
>> Scip mailing list
>> Scip at zib.de
>> https://listserv.zib.de/mailman/listinfo/scip
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> https://listserv.zib.de/mailman/listinfo/scip