[Scip] How to deal with "branching decisions"

[Tobias Achterberg]

You cannot call SCIPchgVarUbNode() from the scip_active() method. The first time the node 
is entered, this will be okay since then the node is the current focus node (the node that 
is currently processed). But if you later leave this part of the tree and then enter it 
again, the node is already a fork node and cannot be modified anymore.

In fact, a second change to the bound is also not necessary, since your first change is 
already added to the node's bound change list and thus redone automatically if the node is 
entered again.

If the only purpose of these constraints is to fix the bounds of some variables to zero, 
then you actually do not need these constraints. You can just fix the bounds of the 
variables in the child node of the branching (i.e., instead of calling SCIPaddConsNode(), 
just call SCIPchgVarUbNode()).

My suggestion to add such dummy constraints was because I thought that you also need to 
update some internal data structure, for example a graph. Maybe, if you branch on an edge, 
then in the left child, you want to remove this edge locally from the graph, while in the 
right child you want to shrink the edge (i.e., replace the two nodes by one big node). If 
you need something like this, then such dummy constraints are handy, since with the 
scip_active() and scip_deactive() methods you can implement the "do" and "undo" operations 
on your graph. But as I said, local changes to the bounds of the variables are 
automatically tracked by SCIP, and you do not need to add dummy constraints for this purpose.


Best,

Tobias


E. van der Veen wrote:
> Hi all,
> 
> To enforce branching decisions in SCIP, I applied an approach suggested 
> by Tobias (which is described below).
> 
> I created a class derived from ObjConshldr for this. When a branching 
> node is created one or multiple constraints are added to the created 
> node. When the node is entered the scip_active (==CONSACTIVE) method is 
> called. In this method variables which are not valid in the node are 
> fixed to zero, via SCIPchgVarUb().
> Now, when I run SCIP it runs for a few seconds, in which branches are 
> created, where constraints are added, and also UBs of vars are set to 0, 
> and released again, but at some point when a node is entered SCIP 
> prompts the following assertion failure:
> 
> Assertion failed: (SCIP_NODETYPE)node->nodetype == 
> SCIP_NODETYPE_FOCUSNODE || (S
> CIP_NODETYPE)node->nodetype == SCIP_NODETYPE_PROBINGNODE || 
> (SCIP_NODETYPE)node-
>> nodetype == SCIP_NODETYPE_CHILD || (SCIP_NODETYPE)node->nodetype == 
>> SCIP_NODETY
> PE_REFOCUSNODE || node->depth == 0, file 
> d:\egbertv\thesis\databases_en_software
> \scip\zibopt\scip-1.00\src\scip\tree.c, line 1541
> 
> and I do not quite see what the issue is here. Some details (but I'm not 
> sure which details you need, but anyways):
> -It happens after a certain node is activated for the 2nd time (so node 
> is activated once, deactived once, and after it is activated again I get 
> the error; I defined SCIP_DEBUG in tree.c)
> -I tried SCIPchgVarUbNode() iso SCIPchgVarUb() (for which I included the 
> node where the constraint is added in the consdata), but I see that this 
> eventually also (just like SCIPchgVarUb()) calls SCIPnodeAddBoundinfer() 
> in tree.c where the assertion failure occurs; In both cases (with 
> SCIPchgVarUbNode() and SCIPchgVarUb()) the same thing happens.
> -The scip_deactive (==CONSDEACTIVE) method of my class only contains 
> SCIP_OKAY, since I figured if SCIP leaves a node bounds of vars are 
> automatically reset, due to the stickingatnode = TRUE flag I set for my 
> constraints
> (the other parameters of the constraints are set to:
> (initial=FALSE separate=FALSE enforce=FALSE check=FALSE propagate=TRUE 
> local=TRUE modifiable=FALSE dynamic=TRUE removable=FALSE) in my 
> constraint handler class I (only) defined scip_delete, scip_trans, 
> scip_enfolp, scip_enfops, scip_check, scip_prop, scip_lock, scip_active, 
> scip_deactive.
> 
> Because, I think it might be useful, I added some debugging information 
> which I get by including #define SCIP_DEBUG to the tree.c file. If you 
> need more debugging information in order to help me, please say so and 
> I'll provide it.
> 
> NB. I also tried another approach suggested by Tobias for enforcing my 
> branching decisions with set packing constraints, but this is not valid 
> anymore due to a remodelling of my problem, where I had to remodel 
> binary vars as general non-negative integer vars. Hence, I'm now trying 
> this approach.
> 
> Any help is very much appreciated!
> 
> Best regards,
> Egbert van der Veen
> 
> 
> ===
>> 2. Sometimes, pricing algorithms need to update their internal data 
>> structures (for example, a graph) after the branching and undo these 
>> updates if the search leaves the child node again.
>>
>> To do this in SCIP, I usually recommend to add "marker constraints" to 
>> the branching nodes. Create a new constraint handler with constraint 
>> data that can store the information necessary to do/undo the changes 
>> in the pricer's data structures. All methods of the constraint handler 
>> (check, enforcing, separation, propagation, ...) should be empty 
>> (which means to always return status = SCIP_FEASIBLE for the 
>> fundamental callbacks), just as if all constraints of this type are 
>> always feasible. The important callbacks are the CONSACTIVE and 
>> CONSDEACTIVE methods.
>>
>> The CONSACTIVE method is always called when a node is entered on which 
>> the constraint has been added (i.e., the child node on which you 
>> applied your branching). Here, you will apply the changes to your 
>> pricing data structures. The CONSDEACTIVE method will be called if the 
>> node is left again. Since the CONSACTIVE and CONSDEACTIVE methods of 
>> different constraints are always called in a stack-like fashion, this 
>> should be exactly what you need.
>>
>> If you have such a constraint handler, just create and add constraints 
>> of this type to the child node of your branching. Make sure to set the 
>> "stickingatnode" flag to TRUE in order to prevent SCIP from moving the 
>> constraint around in the tree.
> 
> ===
>  
> 
> 
> ------------------------------------------------------------------------
> 
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip