[Scip] How to deal with "branching decisions"

Tobias Achterberg achterberg at zib.de
Fri Nov 28 10:23:15 MET 2008



gamrath at zib.de wrote:
> Tobias Achterberg schrieb:
>> This is easy: use the constraints as you do, but instead of fixing the
> variables to zero
>> in the scip_active() method, do so in the scip_prop() method, i.e., the
> domain propagation
>> callback. This is exactly where this stuff belongs to. Just make sure
> that your constraint
>> handler has a propagation frequency of 1, such that the propagator is
> always called.
>>
>> Tobias
>>
> 
> 
> In addition to that, you have to make sure that the node is propagated
> again, if it is entered again. Normally, the propagation method is only
> called once, only when the node is entered the first time.
> You could remember the number of variables that existed, the last time the
> constraint was propagated. Each time it is activated, you can check
> whether new variables were created in the meantime and it should be
> propagated again. You can mark the node at which the constraint is
> sticking to be propagated again by SCIPrepropagateNode(). In the
> propagation callback, you can then fix variables to zero by SCIPchgVarUb()
> and update the number of variables for the last propagation.
> 
> This is also done in the Coloring example of the current SCIP-release in
> the file cons_storeGraph.c.

I don't think that this is true. The default behavior should be that at each node all 
active constraints are propagated. Of course, this would be very time consuming which is 
why all the existing constraint handlers mark their constraints that are already 
propagated and watch for bound change events on the variables in order to clear the mark 
and let the propagator propagate the constraint again.



Tobias


More information about the Scip mailing list